Złożoność przestrzenna algorytmu Coppersmitha

Algorytm Coppersmitha – Winograda jest asymptotycznie najszybszym znanym algorytmem do mnożenia dwóch macierzy kwadratowych. Czas działania ich algorytmu to który jest najlepiej znany do tej pory. Jaka jest złożoność przestrzeni tego algorytmu? Czy to jest w ? $n \times n$ $O(n^{2.376})$ $\Theta(n^2)$

ds.algorithms matrices

— Shiva Kintali
źródło

Tak, wszystkie algorytmy wywodzące się z oryginalnego algorytmu Strassena (obejmuje to najbardziej znane algorytmy mnożenia macierzy , ale nie wszystkie - patrz komentarze) mają złożoność przestrzeni . Jeśli można znaleźć algorytm czasu z przestrzeni złożoności, byłby to wielki postęp. Jedna aplikacja to czas, $n^{3-\varepsilon}$ $\Theta(n^2)$ $n^{3-\varepsilon}$ $poly(\log n)$ $2^{(1-\varepsilon)n}$ algorytm przestrzenny dla problemu sumy częściowej. $poly(n)$

Istnieją jednak pewne przeszkody dla takiego wyniku. W przypadku niektórych modeli obliczeniowych istnieją dość silne dolne granice iloczynu macierzy w czasie i przestrzeni. Odniesienia takie jak Yesha i Abrahamson dadzą ci więcej informacji.

— Ryan Williams
źródło

Cześć Ryan, Awesome. Co z algorytmami teoretycznymi grupowymi Cohna-Umansa [FOCS2003] i Cohna-Kleinberga-Szegedy-Umansa [FOCS2005]?

— Shiva Kintali,

Tak, te też. Rozumiem, że wykonują one specjalny rodzaj splotu (FFT nad specjalną grupą), ale splot dotyczy przedmiotów o wielkości

. Żadne algorytmy małej przestrzeni (o złożoności czasowej lepszej niż algorytm oczywisty) nie są znane dla splotów wektorów nad liczbami całkowitymi i wyobrażam sobie, że trudniej jest uzyskać sploty małych przestrzeni w tych grupach.

Θ (n^{2})

$\Theta(n^2)$

— Ryan Williams

Jak można mieć

miejsce wtedy, gdy przyjmuje

miejsca na przechowywanie danych matryc?

p o l y (l o g n)

$poly(logn)$

2 n^{2}

$2n^{2}$

— T ....

Ponieważ w zwykły sposób, w jaki mierzy się złożoność przestrzeni, dane wejściowe nie są liczone do granicy przestrzeni. Dane wejściowe są traktowane jako „tylko do odczytu” i mierzymy, ile dodatkowej pamięci „do odczytu i zapisu” potrzeba do obliczenia funkcji. W tym przypadku, tylko

dodatkowa przestrzeń jest wystarczająca, gdy pozycje wejściowe ograniczona (na przykład 0 lub 1), użycie

działania.

O (l o g n)

$O(log n)$

O (n^{3})

$O(n^3)$

— Ryan Williams

Nie wiem, co masz na myśli, ale na pewno istnieją „kombinatoryjne” (przeglądanie tabel) alg dla macierzy boolowskiej mult, które pobiły czas n ^ 3 przez czynniki log i zużywają znacznie mniej niż n ^ 2 miejsca ...

— Ryan Williams,

Złożoność przestrzenna algorytmu Coppersmitha – Winograda