Speicherbedarf für schnelle Matrixmultiplikation

12

Angenommen, wir wollen n×n Matrizen multiplizieren . Der langsame Matrixmultiplikationsalgorithmus läuft in der Zeit O(n3) und verwendet den O(n2) -Speicher. Die schnellste Matrixmultiplikation läuft in der Zeit nω+o(1) , wobei ω 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ω ohgr; -Speicher verbraucht . Gibt es eine Garantie dafür, dass dies im O(n2) -Speicher möglich ist? Ist es der Fall, dass die derzeit bekannten Matrixmultiplikationsalgorithmen O(n2) -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.)

David Harris
quelle

Antworten:

16

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-AlgorithmusO(n2)

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(n2)K×KKcc<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.KcL1,,LKcAKcR1,,RKcB

  2. Es vermehrt jene Linearkombinationen , dannLiRi

  3. Es multipliziert die Einträge von mit verschiedenen Skalaren und addiert dann alle diese Matrizen eintragsweise auf, um A B zu erhalten .LiRiAB

(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 iR 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,,KcLiRiABO(K2)

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 - 1 (K×KK×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 )K1×K1K×KO(K2)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 2 istK×KK1×K1S(1)S()S(1)+O(K2)S(1)=2K2löst sich zu .S()O(K2)

Ryan Williams
quelle
Für jeden Strassen-Algorithmus scheint mir dies richtig zu sein. Aber Coppersmith-Winograd auch bewiesen , dass zu bekommen unten erfordert tatsächlich eine unendliche Folge von Strassen-style - Algorithmen, von denen jeder kommt näher und näher an den wahren Exponenten. Tatsächlich liefern sowohl der CW-Algorithmus als auch der CU-Algorithmus solche Sequenzen (wenn auch , soweit wir wissen, nicht in der Nähe von ω ). Über die Rationen hinweg ist es möglich, dass die in einer solchen Sequenz verwendeten Konstanten sehr schnell wachsen, so dass "das" n & ohgr;nωωnω Algorithmus könnte am Ende mit Raum. ω(n2)
Joshua Grochow
1
... Aber durch dein Argument kann man immer einen Algorithmus in Zeit und Raum O ( n 2 ) erhaltenO(nω+δ)O(n2) für jedes . δ>0
Joshua Grochow
@Joshua, der Speicherbedarf dieser Strassen-Algorithmen ist wie , wobei i die Indexnummer des Algorithmus ist und f berechenbar ist. Also, wenn Sie diese Algorithmen suchen über von i = 0 , . . . , K und k eine langsam wachsende Funktion von n ist, dann wird die Arbeit n ω + O ( 1 ) und der Speicher ist n 2 + O ( 1 ) . f(i)n2i=0,...,knω+o(1)n2+o(1)
David Harris
@DavidHarris: Nun, sicher, solange im Vergleich zu f langsam genug wächst , muss k höchstens so schnell wachsen wie f - 1 . Die Frage ist für jede Familie, was f ist und wie schnell k wächst. Aber es gibt keine Garantie, dass k langsam genug wächst, um insgesamt n 2 + o ( 1 ) Speicherauslastung zu erhalten ...kfkf1fkkn2+o(1)
Joshua Grochow
@Joshua. Die Idee ist, dass wir bei Eingaben der Länge die ersten k mutmaßlichen Strassen-Algorithmen durchsuchen , überprüfen, ob sie gültig sind, und diejenige auswählen, die am schnellsten ist. Wählen Sie einfach k als eine Funktion von n , so dass f ( k ( n ) ) = n o ( 1 ) . Da k ( n ) , bedeutet dies, dass jeder Algorithmus vom Strassen-Typ n ausreichend groß gewählt wird. Die Zeit geht also nach n ω + o ( 1nkknf(k(n))=no(1)k(n)nnω+o(1)
4

pO(n2/p)

Alexander Tiskin
quelle