Definicja wykładnika mnożenia macierzy

15

Potocznie definicja wykładnika mnożenia macierzy jest najmniejszą wartością, dla której znany jest algorytm mnożenia macierzy . Nie jest to dopuszczalne, formalnej definicji matematycznej tak Chyba określenie techniczne jest czymś w infimum na wszystkich tak, że istnieje algorytm mnożenia macierzy w . $\omega$ $n^{\omega}$ $t$ $n^t$

W tym przypadku nie możemy powiedzieć, że istnieje algorytm mnożenia macierzy w lub nawet , po prostu że dla wszystkich istnieje algorytm w . Często jednak artykuły i wyniki wykorzystujące mnożenie macierzy podają swój koszt jako po prostu . $n^{\omega}$ $n^{\omega + o(1)}$ $\epsilon > 0$ $n^{\omega + \epsilon}$ $O(n^{\omega})$

Czy istnieje jakaś alternatywna definicja która pozwala na to użycie? Czy są jakieś wyniki, które gwarantują, że musi istnieć algorytm czasu lub ? A może użycie po prostu niechlujne? $\omega$ $n^{\omega}$ $n^{\omega + o(1)}$ $O(n^{\omega})$

ds.algorithms linear-algebra

— David Harris
źródło

2

Jeśli chcesz po prostu użyć mnożenia macierzy jako czarnej skrzynki, najprostszym sposobem jest powiedzenie „Niech będzie takie, abyśmy mogli pomnożyć matrycy za pomocą operacji arytmetycznych ”. Oczywiście nie jest wtedy wykładnikiem mnożenia macierzy, ale może być dowolnie zamknięty. Jeśli chcesz podać wykładnik ostatecznego biegu w postaci dziesiętnej, obecnie i tak musisz zaokrąglić, ponieważ wszystkie nietypowe szacunki dla których wiem, są albo liczbami nieracjonalnymi, albo nieskończonymi sekwencjami.

ω

$\omega$

n \times n

$n \times n$

O (n^{ω})

$O(n^\omega)$

ω

$\omega$

ω

$\omega$

— Markus Bläser

2

ω

$\omega$ jest zwykle definiowana jako minimum dla wszystkich liczb rzeczywistych dla idących do tak że istnieje algorytm czasowy , który zwielokrotnia dwie macierze (gdzie czas jest liczbą dodatków, mnożenia i podziały w polu bazowym). Oznacza to również, że technicznie zawsze powinniśmy pisać ale robi się bałagan, więc kiedy zobaczysz , powinieneś pomyśleć gdzie to środowisko uruchomieniowe algorytmu mnożenia macierzy.

k

$k$

n

$n$

\infty

$\infty$

O (n^{k})

$O(n^k)$

n \times n

$n\times n$

n^{ω + o (1)}

$n^{\omega+o(1)}$

O (n^{ω})

$O(n^\omega)$

O (M (n))

$O(M(n))$

M (n)

$M(n)$

— virgi

20

Wykładnik mnożenia macierzy będący nie gwarantuje, że istnieje algorytm działający w czasie , ale tylko, że dla każdego istnieje algorytm działający w . Rzeczywiście, jeśli możesz znaleźć algorytm działający w czasie , oznacza to, że . $\omega$ $O(n^\omega)$ $\epsilon > 0$ $O(n^{\omega+\epsilon})$ $O(n^2 \mathrm{polylog}(n))$ $\omega = 2$

Formalną definicję można znaleźć w książce Teoria złożoności algebraicznej autorstwa Petera Bürgissera, Michaela Clausena, Amina Shokrollahi.

— MCH
źródło

7

Drobny komentarz, który jest zbyt długi, aby być komentarzem:

Czasami, gdy masz problem, dla którego istnieje algorytm z czasem działania dla każdego , istnieje algorytm z czasem działania . $O(n^{k+\epsilon})$ $\epsilon>0$ $n^{k+o(1)}$

Na przykład czasami otrzymujesz algorytmy, które działają jak dla niektórych szybko rosnących funkcji (jak ). Jeśli ustawisz na (powiedzmy) , to będzie o (1). W przykładzie, w którym wynosi , możesz wybrać $f(1/\epsilon)n^{k+\epsilon}$ $f$ $2^{2^{1/\epsilon}}$ $f(1/\epsilon)$ $\log n$ $\epsilon$ $f(1/\epsilon)$ $2^{2^{1/\epsilon}}$ $1/\epsilon$ być , co daje , co oznacza o (1). Tak więc końcowy czas działania tego algorytmu będzie wynosił , ponieważ jest również . $\log \log \log n$ $\epsilon = 1/ (\log \log \log n)$ $n^{k+o(1)}$ $\log n$ $n^{o(1)}$

— Robin Kothari
źródło

Czy wyobrażam sobie, że algorytm Coppersmith-Winograd należy do tej kategorii?

— David Harris

2

@DavidHarris: Nie wiem o tym. Może ktoś, kto rozumie algorytm, może rzucić na to trochę światła. Chciałem tylko powiedzieć, że często

nie jest tak złe, jak się wydaje.

O (n^{k + ϵ})

$O(n^{k+\epsilon})$

— Robin Kothari,

5

Jest dobrze znany wynik Coppersmitha i Winograda, że czas nie może być zrealizowany przez żaden pojedynczy algorytm. Ale przeczytałem , że ograniczają się do algorytmów opartych na dwubiegunowych tożsamościach podobnych do Strassena, więc nie wiem na pewno, ponieważ papier jest za zaporą. $O(n^{\omega})$

— Diego de Estrada
źródło

3

Nie zgadzam się z twoim stwierdzeniem w pytaniu, że nie jest dobrze zdefiniowane przez „najmniejszą wartość, dla której istnieje znany algorytm mnożenia macierzy ”. Gdy ludzie używają tej stałej, dzieje się tak dlatego, że ich algorytm opiera się na mnożeniu macierzy, a przez złożoność , mają na myśli „optymalną złożoność naszego algorytmu zapewnia optymalny algorytm mnożenia macierzy”. $\omega$ $n^ω$ $n^\omega$

Nie twierdzę, że inaczej nie można zdefiniować (np. Twierdzenie, że jest najlepszą możliwą do osiągnięcia złożonością). $\omega$ $\omega$

Btw, najbardziej znana górna granica mnożenia macierzy została właśnie poprawiona do jeśli się nie mylę. $2.3737$

— Bruno
źródło

3

Nie rozumiem, w jaki sposób wiedza ludzka może być częścią definicji matematycznej

— David Harris,

2

Ostatnie doświadczenia pokazują, że znacznie łatwiej jest obliczyć wszystkie algorytmy niż wszystkie algorytmy obecnie znane ludzkości ;-)

— Markus Bläser 30.11.11