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

Der Algorithmus

Vereinfachend wird der Spezialfall quadratischer Matrizen mit 2^{k} Zeilen bzw. Spalten betrachtet.

Seien also {\displaystyle A,B\in R^{2^{k}\times 2^{k}}} Matrizen über einem Ring R und ferner ihr Produkt {\displaystyle C=A\cdot B\in R^{2^{k}\times 2^{k}}}. Diese lassen sich auch als Blockmatrizen

{\displaystyle 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}}}

betrachten, wobei {\displaystyle A_{i,j},B_{i,j},C_{i,j}\in R^{2^{k-1}\times 2^{k-1}}} sind.

Für die Multiplikation von Blockmatrizen 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}}

Die direkte Berechnung der {\displaystyle C_{i,j}} benötigt also 8 (aufwändige) Matrizenmultiplikationen. Um diese Anzahl zu reduzieren, berechnet der Algorithmus von Strassen 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} sind lediglich 7 Multiplikationen nötig, die C_{{ij}} lassen sich nun durch Additionen (und Subtraktionen) ermitteln:

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}}

Für die Multiplikationen in der Berechnung der M_{i} wird obiges Verfahren rekursiv ausgeführt, bis das Problem auf die Multiplikation von Skalaren reduziert ist.

In der Praxis kann die gewöhnliche Multiplikation für kleine Matrizen durchaus schneller sein. Daher bietet sich ein Wechsel zur gewöhnlichen Multiplikation anstelle eines rekursiven Aufrufs an, sobald die Matrizendimensionen klein genug sind (Cut-Off).

Die linke Spalte repräsentiert eine 2\times 2 Matrizenmultiplikation. Jede andere Spalte repräsentiert eine der 7 Multiplikationen des Strassen-Algorithmus.

Aufwand

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.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 29.12. 2020