Welche Intuition steckt hinter Straßens Algorithmus?
Ich bin auf Straßens Algorithmus zur Matrixmultiplikation gestoßen, der zeitlich komplex ist$O(n^{2.81})$, deutlich besser als die naiven $O(n^3)$. Natürlich gab es seit Strassen einige andere Verbesserungen bei der Matrixmultiplikation, aber meine Frage ist spezifisch für diesen Algorithmus.
Wenn Sie den Algorithmus sehen , werden Sie feststellen, dass 7 Matrizen$M_1$ zu $M_7$wurden als Zwischenberechnungsschritte definiert, und das endgültige Matrixprodukt kann in diesen ausgedrückt werden. Ich verstehe, wie man diese Behauptung verifiziert und zum Ausdruck für die gewünschte Zeitkomplexität gelangt, aber ich kann die Intuition hinter diesem Algorithmus nicht erfassen , dh warum sind die Matrizen$M_1$ durch $M_7$ definiert wie sie sind?
Vielen Dank!
Antworten
Die eigentliche Antwort auf diese Frage lautet: Wenn Sie lange genug damit spielen, werden Sie einen Algorithmus treffen, der 7 Multiplikationen erfordert - nicht unbedingt der gleiche wie der von Strassen, aber in gewissem Sinne ein äquivalenter: Es ist bekannt, dass alle diese Algorithmen sind äquivalent, wie de Groote in seiner Arbeit von 1978 über verschiedene optimale Algorithmen für die Berechnung bilinearer Abbildungen gezeigt hat. II. Optimale Algorithmen für die 2 × 2-Matrix-Multiplikation .
In der Literatur gibt es viele Versuche zu erklären, wie man einen solchen Algorithmus entwickeln könnte, zum Beispiel:
- Gideon Yuval, Ein einfacher Beweis für Straßens Ergebnis , 1978. Wir erklären diesen Ansatz unten.
- Ann Q. Gates, Vladik Kreinovich, Straßens Algorithmus (etwas natürlicher): Eine pädagogische Bemerkung , 2001. Die Idee ist, Symmetrien zu verwenden, um die linearen Kombinationen zu erraten, die einer der zu multiplizierenden Matrizen entsprechen, und sie dann intelligent zu koppeln lineare Kombinationen der anderen Matrix.
- Jacob Minz, Herleitung des Strassen-Algorithmus zur Multiplikation von 2 × 2-Matrizen , 2015. Die Idee ist, lineare Transformationen anzuwenden, um ein einfacher aussehendes Problem zu erhalten, und es dann von Hand zu lösen.
- Christian Ikenmeyer, Vladimir Lysikov, Strassens 2x2-Matrixmultiplikationsalgorithmus: Eine konzeptionelle Perspektive , 2017. Die Idee ist, eine Grundlage für die$2\times 2$ spurlose Matrizen und verwenden Sie ihre Multiplikationstabelle, um den Strassen-Algorithmus zu konstruieren.
- Joshua A. Grochow, Christopher Moore, Entwurf des Strassen-Algorithmus , 2017. Die Idee ist, mit Vektoren zu beginnen, die die Eckpunkte eines gleichseitigen Dreiecks in der Ebene bilden, und die elementaren Eigenschaften dieser Vektoren zu verwenden, um einen Algorithmus zu entwickeln.
Gideon Yuval zeigt, wie Sie den Strassen-Algorithmus entwickeln können. Der Ausgangspunkt besteht darin, die Matrixmultiplikation in das Problem der Berechnung eines Matrixvektorprodukts umzuwandeln: die Berechnung$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \end{pmatrix} $$ ist das gleiche wie Computing $$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & c & 0 \\ 0 & d & 0 & d \end{pmatrix} \times \begin{pmatrix} e \\ f \\ g \\ h \end{pmatrix} $$ Angenommen, wir könnten die Matrix links als Summe schreiben $\ell_1 M_1 + \cdots + \ell_7 M_7$, wo $\ell_i$ ist eine lineare Kombination von $a,b,c,d$ und $M_i$ ist beispielsweise eine Rang-1-Matrix $M_i = x_i y_i^T$. Das Produkt, nach dem wir suchen, ist also$$ \sum_{i=1}^7 \ell_i M_i \begin{pmatrix} c\\d\\e\\f \end{pmatrix} = \sum_{i=1}^7 \ell_i x_i y_i^T \begin{pmatrix} c\\d\\e\\f \end{pmatrix} = \sum_{i=1}^7 \ell_i r_i x_i, $$ wo $r_i$ ist eine lineare Kombination von $e,f,g,h$. Dies zeigt, dass jeder Eintrag in der Produktmatrix eine lineare Kombination der Produkte ist$\ell_i,r_i$.
Lassen Sie uns nun zeigen, wie man die Zersetzung finden kann. Wir beginnen damit, die Einträge oben links und unten rechts so zu löschen, dass keine Einträge auf Null gesetzt werden:$$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & d & 0 \\ 0 & c & 0 & d \end{pmatrix} = \begin{pmatrix} a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \\ a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \\ 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & a-d & 0 & b-d \\ c-a & 0 & d-a & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} $$ Dies führt zu einem Durcheinander, das wir zu beheben versuchen, indem wir das innere Quadrat "umdrehen": $$ \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & a-d & 0 & b-d \\ c-a & 0 & d-a & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & a-d & a-d & 0 \\ 0 & d-a & d-a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & d-a & b-d \\ c-a & a-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} $$ Schon seit $d-a = (b-a)-(b-d)$ und $a-d = (c-d)-(c-a)$ist es einfach, die letzte Matrix als Summe von vier Rang-1-Matrizen darzustellen: $$ \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & d-a & b-d \\ c-a & a-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & b-a & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & d-b & b-d \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & c-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ c-a & a-c & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$ Insgesamt erhalten wir folgende Darstellung: $$ \begin{pmatrix} a & 0 & b & 0 \\ 0 & a & 0 & b \\ c & 0 & d & 0 \\ 0 & c & 0 & d \end{pmatrix} = \begin{pmatrix} a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \\ a & 0 & a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \\ 0 & 0 & 0 & 0 \\ 0 & d & 0 & d \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & a-d & a-d & 0 \\ 0 & d-a & d-a & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & b-a & 0 \\ 0 & 0 & b-a & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & d-b & b-d \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & c-d & 0 & 0 \\ 0 & c-d & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ c-a & a-c & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$
Es ist ziemlich offensichtlich, dass Sie einen asymptotisch schnelleren Algorithmus erhalten, wenn Sie ein 2x2-Matrixprodukt mit 7 Multiplikationen und einigen Additionen berechnen können. Sie benötigen 8 Produkte. Aber zum Beispiel (a + b) * (c + d) ergibt die Summe von vier Produkten mit einer Multiplikation.
So könnte es möglich sein, viele Produkte mit sieben Multiplikationen so zu berechnen, dass sich alle unerwünschten Produkte gegenseitig aufheben. Ich weiß nicht, wie viele Produkte er ausprobiert hat, die am Ende nicht geklappt haben.