Strassen-Algorithmus

Der Strassen-Algorithmus (nach Volker Strassen) ist ein Algorithmus aus der Linearen Algebra und wird zur Matrizenmultiplikation verwendet. Der Strassen-Algorithmus realisiert die Matrix-Multiplikation asymptotisch effizienter als das Standardverfahren und ist in der Praxis für große Matrizen schneller.

Der Algorithmus

Vereinfachend gehen wir von zwei quadratischen Matrizen A,B über einem Ring R aus. Des weiteren haben A und B die Größe 2ⁿ und C sei das Produkt von A und B.

$C=A\cdot B\qquad A,B,C\in R^{2^{n}\times 2^{n}}$

Nun kann man A,B,C auch als Blockmatrizen betrachten:

$A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}},\qquad B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix}},\qquad C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}},\qquad A_{ij},B_{ij},C_{ij}\in K^{2^{n-1}\times 2^{n-1}}$

Nun gilt:

$C_{1,1}=A_{1,1}\cdot B_{1,1}+A_{1,2}\cdot B_{2,1}$

$C_{1,2}=A_{1,1}\cdot B_{1,2}+A_{1,2}\cdot B_{2,2}$

$C_{2,1}=A_{2,1}\cdot B_{1,1}+A_{2,2}\cdot B_{2,1}$

$C_{2,2}=A_{2,1}\cdot B_{1,2}+A_{2,2}\cdot B_{2,2}$

Berechnet man die $C_{ij}$ mit diesen Formeln so benötigt man 8 (teure) Matrizenmultiplikationen. Um die Anzahl der Multiplikationen zu reduzieren berechnet man folgende Hilfsmatrizen:

$M_{1}:=(A_{1,1}+A_{2,2})\cdot (B_{1,1}+B_{2,2})$

$M_{2}:=(A_{2,1}+A_{2,2})\cdot B_{1,1}$

$M_{3}:=A_{1,1}\cdot (B_{1,2}-B_{2,2})$

$M_{4}:=A_{2,2}\cdot (B_{2,1}-B_{1,1})$

$M_{5}:=(A_{1,1}+A_{1,2})\cdot B_{2,2}$

$M_{6}:=(A_{2,1}-A_{1,1})\cdot (B_{1,1}+B_{1,2})$

$M_{7}:=(A_{1,2}-A_{2,2})\cdot (B_{2,1}+B_{2,2})$

Zur Berechnung der $M_{i}$ benötigt man nur 7 Multiplikationen und nun kann man die $C_{ij}$ nur durch Additionen (und Subtraktionen) berechnen:

$C_{1,1}=M_{1}+M_{4}-M_{5}+M_{7}$

$C_{1,2}=M_{3}+M_{5}$

$C_{2,1}=M_{2}+M_{4}$

$C_{2,2}=M_{1}-M_{2}+M_{3}+M_{6}$

Diese Idee verwendet man nun auch für die Multiplikationen zur Berechung der $M_{i}$ und iteriert das ganze solange bis man nur noch Skalare multipliziert.

Bei der praktischen Implementierung iteriert man für gewöhnlich nur solange bis die Matrix -Dimension so klein ist, dass der Standard-Algorithmus zur Matrizen Multipliaktion effizienter ist und verwendet dann diesen.

Siehe auch

Coppersmith–Winograd Algorithmus

Weblinks

• Eric W. Weisstein: Strassen's Formulas. In: MathWorld (englisch).