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

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 , $\mathbf{A}$$\mathbf{B}$$\mathbf{A}$$\mathbf{B}$$2 \times 2$$7$$8$$\mathbf{C}=\mathbf{A} \mathbf{B}$ dann haben wir C 1 , 1 = A 1 , 1 B 1 , 1 + A

$$\mathbf{A} =\begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}$$ , die erfordert8Multiplikationen. Stattdessen berechnen wir in Strassen M 1 :=( A 1 , 1 + A 2 , 2 )( B 1 , 1 + B 2 , 2 $$\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}\\ \mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,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 $$\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})\\ \mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}\\ \mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})\\ \mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})\\ \mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}\\ \mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})\\ \mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$$ $\mathbf{C}_{i,j}$$\mathbf{M}_{k}$ 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 : $$\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}\\ \mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}\\ \mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}\\ \mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$$ $\mathbf{M}_k$$\mathbf{A}$$\mathbf{B}$$\mathbf{M}_k$$\mathbf{A}_{i,j}$$\mathbf{B}_{i,j}$$\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$$\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$$\mathbf{M}_k$

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

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 \times 2$-Matrizen mit 7 Multiplikationen bis zur Äquivalenz. Dies könnte ein einzigartiges Merkmal von sein$2 \times 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 \times 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.

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 beginnen$A_0,A_1,A_2,A_3$ und $B_0,B_1,B_2,B_3$ des Raumes von $2\times 2$ reelle Matrizen, die folgende Eigenschaft erfüllen: $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$. Außerdem,$A_0 = B_0$. Zwei Matrizen multiplizieren$A$ 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 ($A_0=B_0,A_1,A_2,A_3,B_1,B_2,B_3$) werden nur sieben Produkte benötigt. Das$M$ 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.