Speicherbedarf für schnelle Matrixmultiplikation

Angenommen, wir wollen $n \times n$ Matrizen multiplizieren . Der langsame Matrixmultiplikationsalgorithmus läuft in der Zeit $O(n^3)$ und verwendet den $O(n^2)$ -Speicher. Die schnellste Matrixmultiplikation läuft in der Zeit $n^{\omega + o(1)}$ , wobei $\omega$ die lineare Algebra konstant, aber was um seinen Speicher Komplexität bekannt?

Es scheint möglich zu sein, dass eine schnelle Matrixmultiplikation a priori $n^{\omega}$ ohgr; -Speicher verbraucht . Gibt es eine Garantie dafür, dass dies im $O(n^2)$ -Speicher möglich ist? Ist es der Fall, dass die derzeit bekannten Matrixmultiplikationsalgorithmen $O(n^2)$ -Speicher verwenden?

(Eigentlich interessiert mich die rechteckige Matrixmultiplikation, aber ich gehe davon aus, dass die Antwort in diesem Fall dieselbe ist wie für den quadratischen Fall, und der quadratische Fall ist besser untersucht.)

Die Raumnutzung beträgt für alle Strassen-ähnlichen Algorithmen (dh diejenigen, die auf der algebraischen Obergrenze des Rangs der Matrixmultiplikation beruhen ) höchstens ). Siehe Raumkomplexität des Coppersmith-Winograd-Algorithmus$O(n^2)$

In meiner vorherigen Antwort habe ich jedoch festgestellt, dass ich nicht erklärt habe, warum der Speicherplatz . Überlegen Sie, was ein Strassen-ähnlicher Algorithmus bewirkt. Es geht von einem festen Algorithmus für die K × K- Matrixmultiplikation aus, der K c -Multiplikationen für eine Konstante c < 3 verwendet . Insbesondere kann dieser Algorithmus (was auch immer es ist) WLOG so geschrieben werden, dass:$O(n^2)$$K \times K$$K^c$$c < 3$

1. Es berechnet verschiedene Matrizen L 1 , … , L K c, die Einträge der ersten Matrix A mit verschiedenen Skalaren multiplizieren, und K c Matrizen R 1 , … , R K c aus der zweiten Matrix B ähnlicher Form.$K^c$$L_1,\ldots,L_{K^c}$$A$$K^c$$R_1,\ldots,R_{K^c}$$B$

2. Es vermehrt jene Linearkombinationen , dann$L_i \cdot R_i$

3. Es multipliziert die Einträge von mit verschiedenen Skalaren und addiert dann alle diese Matrizen eintragsweise auf, um A ⋅ B zu erhalten .$L_i \cdot R_i$$A \cdot B$

(Dies ist ein sogenannter "bilinearer" Algorithmus, aber es stellt sich heraus, dass jeder "algebraische" Matrixmultiplikationsalgorithmus auf diese Weise geschrieben werden kann.) Für jedes muss dieser Algorithmus nur das speichern aktuelles Produkt L i ⋅ R i und der aktuelle Wert von A ⋅ B (anfangs auf Nullen gesetzt) ​​im Speicher zu einem beliebigen Zeitpunkt, sodass der Platzbedarf O ( K 2 ) ist .$i=1,\ldots,K^c$$L_i \cdot R_i$$A \cdot B$$O(K^2)$

Wenn dieser endliche Algorithmus gegeben ist, wird er auf beliebige -Matrizen erweitert, indem die großen Matrizen in K × K- Blöcke mit den Dimensionen K ℓ - $K^{\ell} \times K^{\ell}$$K \times K$ unter Anwendung des Finite - K × K - Algorithmus zum Block Matrizen und rekursives Aufrufen des Algorithmus, wenn zwei Blöcke multipliziert werden müssen. Auf jeder Rekursionsebene müssen wir nur O ( K 2 ℓ ) Feldelemente im Speicherbehalten(Speichern von O ( 1 $K^{\ell-1}\times K^{\ell-1}$$K \times K$$O(K^{2\ell})$$O(1)$verschiedene Matrizen). Unter die Annahme die Raumnutzung für K l - 1 × K l - 1 Matrizenmultiplikation ist S ( l - 1 ) , wobei der Raum Verwendung dieses rekursiven Algorithmus ist , S ( l ) ≤ S ( l - 1 ) + O ( K 2 l ) , was für S ( 1 ) = 2 K $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$löst sich zu .$S(\ell) \leq O(K^{2\ell})$

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