Strassen-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 schneller für große Matrizen (solche mit einem Rang größer als 1000).

Der Algorithmus[Bearbeiten]

Vereinfachend gehen wir von zwei quadratischen Matrizen A,B über einem Ring R aus. Des Weiteren haben A und B Spalten- und Zeilendimension n=2k 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 Matrizenmultiplikation. Jede andere Spalte repräsentiert eine der 7 Multiplikationen des Strassen-Algorithmus.

Aufwand[Bearbeiten]

Der Standardalgorithmus zur Matrizenmultiplikation 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[1].

Literatur[Bearbeiten]

Referenzen[Bearbeiten]

  1. Webb Miller: Computational complexity and numerical stability. In: SIAM News. 4, 1975, S. 97-107.

Weblinks[Bearbeiten]