Strassen-Algorithmus

Der Strassen-Algorithmus (erfunden vom deutschen Mathematiker Volker Strassen) ist ein Algorithmus aus der Linearen Algebra und wird zur Matrizenmultiplikation verwendet. Der Strassen-Algorithmus realisiert die Matrizenmultiplikation 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 Spalten- und Zeilendimension n=2^k und C sei das Produkt von A und B.

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

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

$A= \begin{pmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{pmatrix} ,\qquad B= \begin{pmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{pmatrix} ,\qquad C= \begin{pmatrix} C_{1,1} & C_{1,2} \\ C_{2,1} & C_{2,2} \end{pmatrix} ,\qquad A_{i,j},B_{i,j},C_{i,j} \in R^{2^{k-1} \times 2^{k-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 Berechnung der $M_i$ und iteriert das ganze so lange, bis man nur noch Skalare multipliziert.

Bei der praktischen Implementierung iteriert man für gewöhnlich nur so lange, bis die Matrixdimension so klein ist, dass der Standard-Algorithmus zur Matrizenmultiplikation effizienter ist, und verwendet dann diesen (Cut-Off).

Die linke Spalte repräsentiert eine 2x2 Matrizenmultplikation. Jede andere Spalte repräsentiert eine der 7 Multiplikationen des Strassen-Algorithmus.

Aufwand

Die Standard-Matrixmultiplikation benötigt

$n^{\log_{2}8}= n^3$

Multiplikationen der Elemente des Ringes R. Wir ignorieren die benötigten Additionen, weil sie, abhängig von R, in Computerimplementationen viel schneller sein können als die Multiplikationen. Mit dem Strassen-Algorithmus können wir die Anzahl der Multiplikationen auf

$n^{\log_{2}7}\approx n^{2,807}$

reduzieren. Die Reduktion der Anzahl der Multiplikationen bezahlt man allerdings mit einer Verringerung der numerischen Stabilität.

Siehe auch

Coppersmith–Winograd Algorithmus bzw. englischer Artikel: Coppersmith–Winograd algorithm

Literatur

• Volker Strassen: Gaussian Elimination is not Optimal. In: Numerische Mathemetik, Bd. 13 (1969), S. 354–356, ISSN 00298-599X.

Weblinks

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