Größeres Bild hinter der Auswahl der Matrizen im Strassen-Algorithmus

17

Beim Strassen-Algorithmus werden zur Berechnung des Produkts zweier Matrizen und B die Matrizen A und B in 2 × 2- Blockmatrizen unterteilt, und der Algorithmus berechnet rekursiv 7- Blockmatrix-Matrix-Produkte im Gegensatz zu einer naiven 8- Blockmatrix. Matrixprodukte, dh wenn wir C = A B wollen , wobei A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , 2EINBEINB2×278C=EINB dann haben wir C 1 , 1 = A 1 , 1 B 1 , 1 + A 1

EIN=[EIN1,1EIN1,2EIN2,1EIN2,2] , B=[B1,1B1,2B2,1B2,2] , C=[C1,1C1,2C2,1C2,2]
, die erfordert8Multiplikationen. Stattdessen berechnen wir in Strassen M 1 :=( A 1 , 1 + A 2 , 2 )( B 1 , 1 + B 2 , 2 )
C1,1=EIN1,1B1,1+EIN1,2B2,1C1,2=EIN1,1B1,2+EIN1,2B2,2C2,1=EIN2,1B1,1+EIN2,2B2,1C2,2=EIN2,1B1,2+EIN2,2B2,2
8 und man erhält C i , j unter Verwendung von M k als C 1 , 1 = M 1 + M 4 - M 5 + M 7
M1: =(EIN1,1+EIN2,2)(B1,1+B2,2)M2: =(EIN2,1+EIN2,2)B1,1M3: =EIN1,1(B1,2-B2,2)M4: =EIN2,2(B2,1-B1,1)M5: =(EIN1,1+EIN1,2)B2,2M6: =(EIN2,1-EIN1,1)(B1,1+B1,2)M7: =(EIN1,2-EIN2,2)(B2,1+B2,2)
Cich,jMk Die Wahl der Matrizen M k erscheint mir jedoch willkürlich. Gibt es ein größeres Bild darüber, warum wir diese spezifischen Produkte der Untermatrizen von A und B auswählen? Außerdem würde ich erwarten, dass M k A i , j und B i , j symmetrischeinbezieht, was hier nicht der Fall zu sein scheint. Zum Beispiel haben wir M 2 :=
C1,1=M1+M4-M5+M7C1,2=M3+M5C2,1=M2+M4C2,2=M1-M2+M3+M6
MkEINBMkEINich,jBich,jM2: =(EIN2,1+EIN2,2)B1,1EIN1,1(B1,2+B2,2)Mk

Ich würde mich freuen, wenn jemand Licht ins Dunkel bringen könnte.

Gemeinschaft
quelle

Antworten:

15

De Groote (Über verschiedene optimale Algorithmen für die Berechnung bilinearer Abbildungen. II. Optimale Algorithmen für die 2x2-Matrix-Multiplikation. Theor. Comput. Sci. 7: 127-148, 1978) beweist, dass es nur einen Algorithmus gibt, der multipliziert werden kann 2×2-Matrizen mit 7 Multiplikationen bis zur Äquivalenz. Dies könnte ein einzigartiges Merkmal von sein2×2-Matrix-Multiplikation. (Hinweis: In der Literatur finden Sie verschiedene Varianten des Strassen-Algorithmus. Sie sind alle gleichbedeutend mit dem richtigen Äquivalenzbegriff.)

Wenn Sie jetzt anfangen, eine Untergrenze für zu beweisen 2×2-Matrix-Multiplikation - siehe das Buch von Bürgisser, Clausen und Shokrollahi, wie das geht - dann zeigt sich ganz natürlich Strassens Algorithmus oder eine Variante. Sie werden eine Menge Identitäten finden, die bestimmen, wie die Produkte aussehen. Dann können Sie mit ein paar Vermutungen fertig werden. (Der Beweis von De Groote zeigt, dass selbst das Raten nicht notwendig ist.)

Schönhage sagte mir einmal, Strassen habe ihm einmal gesagt, dass er seinen Algorithmus auf diese Weise gefunden habe, indem er versucht habe, eine Untergrenze zu beweisen.

Markus Bläser
quelle
11

Das Buch Algebraic Complexity Theory von Bürgisser, Clausen und Shokrollahi (S. 11-12) enthält eine Erklärung. Die Idee ist, mit zwei Basen zu beginnenEIN0,EIN1,EIN2,EIN3 und B0,B1,B2,B3 des Raumes von 2×2 reelle Matrizen, die folgende Eigenschaft erfüllen: EINichBj{0,EIN0,EIN1,EIN2,EIN3,B0,B1,B2,B3}. Außerdem,EIN0=B0. Zwei Matrizen multiplizierenEIN und B, repräsentieren jeden von ihnen in der entsprechenden Basis und bewerten das Produkt. Da nur sieben verschiedene Nicht-Null-Matrizen im Ergebnis erscheinen (EIN0=B0,EIN1,EIN2,EIN3,B1,B2,B3) werden nur sieben Produkte benötigt. DasM Matrizen sind genau diese Basen.

Ich weiß nicht, ob sich Strassen diese Sichtweise einfallen ließ. In Anbetracht der anderen Identitäten, die den Algorithmen für die schnelle Matrixmultiplikation zugrunde liegen, ist nicht klar, ob etwas Tiefes im Gange ist, als nur eine Formel zu erarbeiten. Wir haben das schon einmal durchgemacht - Lagrange verwendete die vierquadratische Identität (die zuvor bekannt war), um den Vierquadratsatz zu beweisen. Zuerst muss es nur eine merkwürdige algebraische Identität gewesen sein, aber jetzt wissen wir, dass sie die Multiplikativitätseigenschaft der Quaternionsnorm angibt. Ob die obige Interpretation so produktiv ist, lässt sich nach heutigem Kenntnisstand nur schwer beurteilen.

Yuval Filmus
quelle
3
Solche Basen werden als M-Paar bezeichnet, siehe Kapitel über Algebren von minimalem Rang im Buch von Bürgisser, Clausen und Shokrollahi. Ich denke, es ist ziemlich schwierig, auf die Idee zu kommen, dass M-Paare existieren, ohne das Alder-Strassen-Theorem zu kennen (siehe das obige Buch). Im Speziellen,2×2-Matrizen sind die einzige Matrixalgebra, für die ein M-Paar existiert.
Markus Bläser