Strassen-Algorithmus

Der Strassen-Algorithmus (benannt nach dem 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_{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 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₁ + M₄ − M₅ + M₇

C_1,2 = M₃ + M₅

C_2,1 = M₂ + M₄

C_2,2 = M₁ − M₂ + M₃ + M₆

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, Numer. Math. 13, S. 354-356, 1969

Weblinks

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