Wymagana pamięć do szybkiego mnożenia macierzy

Załóżmy, że chcemy pomnożyć macierzy. Algorytm powolnego mnożenia macierzy działa w czasie O ( n 3 ) i wykorzystuje pamięć O ( n 2 ) . Najszybsze mnożenie macierzy przebiega w czasie n ω + o ( 1 ) , gdzie ω jest stałą algebry liniowej, ale co wiadomo o jej złożoności pamięci?$n \times n$$O(n^3)$$O(n^2)$$n^{\omega + o(1)}$$\omega$

Wydaje się, że a priori możliwe jest, że szybkie mnożenie macierzy zużywa pamięć . Czy jest jakaś gwarancja, że ​​można to zrobić w pamięci O ( n 2 ) ? Czy to tak, że obecnie znane algorytmy mnożenia macierzy wykorzystują pamięć O ( n 2 ) ?$n^{\omega}$$O(n^2)$$O(n^2)$

(Właściwie interesuje mnie mnożenie macierzy prostokątnej, ale zakładam, że odpowiedź byłaby w tym przypadku taka sama jak w przypadku kwadratu, a przypadek kwadratu jest lepiej zbadany).

Wykorzystanie przestrzeni wynosi co najwyżej dla wszystkich algorytmów podobnych do Strassena (tj. Opartych na górnej granicy algebraicznie mnożącej macierz). Zobacz Złożoność przestrzeni algorytmu Coppersmitha – Winograda$O(n^2)$

$O(n^2)$$K \times K$$K^c$$c < 3$

1. $K^c$$L_1,\ldots,L_{K^c}$$A$$K^c$$R_1,\ldots,R_{K^c}$$B$

2. $L_i \cdot R_i$

3. $L_i \cdot R_i$$A \cdot B$

$i=1,\ldots,K^c$$L_i \cdot R_i$$A \cdot B$$O(K^2)$

$K^{\ell} \times K^{\ell}$$K \times K$$K^{\ell-1}\times K^{\ell-1}$$K \times K$$O(K^{2\ell})$$O(1)$$K^{\ell} \times K^{\ell}$$K^{\ell-1}\times K^{\ell-1}$$S(\ell-1)$$S(\ell) \leq S(\ell-1) + O(K^{2\ell})$$S(1) = 2K^2$$S(\ell) \leq O(K^{2\ell})$

$p$$O(n^2/p)$