2001:4BC9:803:190B:8ACF:8874:9911:A775: Es sollte stets O (groß Oh) stehen

2025-05-17T08:25:16Z

Es sollte stets O (groß Oh) stehen

Neue Seite

Der '''Strassen-Algorithmus''' (erfunden vom deutschen Mathematiker [[Volker Strassen]]) ist ein [[Algorithmus]] aus der [[Lineare Algebra|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 [[Matrix (Mathematik)|Matrizen]] (solche mit einem [[Rang (Lineare Algebra)|Rang]] größer als 1000).

== Der Algorithmus ==
Vereinfachend wird der Spezialfall quadratischer Matrizen mit <math>2^k</math> Zeilen bzw. Spalten betrachtet.

Seien also <math>A, B \in R^{2^k \times 2^k}</math> Matrizen über einem [[Ring (Algebra)|Ring]] <math>R</math> und ferner ihr Produkt <math>C = A \cdot B \in R^{2^k \times 2^k}</math>.
Diese lassen sich auch als [[Blockmatrix|Blockmatrizen]]
: <math>
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}
</math>
betrachten, wobei
<math>A_{i,j}, B_{i,j}, C_{i,j} \in R^{2^{k-1} \times 2^{k-1}}
</math>
sind.

Für die Multiplikation von Blockmatrizen gilt:
: <math>C_{1,1} = A_{1,1}\cdot B_{1,1} + A_{1,2}\cdot B_{2,1} </math>
: <math>C_{1,2} = A_{1,1}\cdot B_{1,2} + A_{1,2}\cdot B_{2,2} </math>
: <math>C_{2,1} = A_{2,1}\cdot B_{1,1} + A_{2,2}\cdot B_{2,1} </math>
: <math>C_{2,2} = A_{2,1}\cdot B_{1,2} + A_{2,2}\cdot B_{2,2} </math>
Die direkte Berechnung der <math>C_{i,j}</math> benötigt also <math>8</math> (aufwändige) Matrizenmultiplikationen. Um diese Anzahl zu reduzieren, berechnet der Algorithmus von Strassen folgende Hilfsmatrizen:
: <math>M_{1} := (A_{1,1} + A_{2,2})\cdot (B_{1,1} + B_{2,2})</math>
: <math>M_{2} := (A_{2,1} + A_{2,2})\cdot B_{1,1}</math>
: <math>M_{3} := A_{1,1} \cdot(B_{1,2} - B_{2,2})</math>
: <math>M_{4} := A_{2,2} \cdot(B_{2,1} - B_{1,1})</math>
: <math>M_{5} := (A_{1,1} + A_{1,2})\cdot B_{2,2}</math>
: <math>M_{6} := (A_{2,1} - A_{1,1}) \cdot(B_{1,1} + B_{1,2})</math>
: <math>M_{7} := (A_{1,2} - A_{2,2}) \cdot(B_{2,1} + B_{2,2})</math>
Zur Berechnung der <math>M_i</math> sind lediglich <math>7</math> Multiplikationen nötig, die <math>C_{ij}</math> lassen sich nun durch [[Addition]]en (und [[Subtraktion]]en) ermitteln:
: <math>C_{1,1} = M_{1} + M_{4} - M_{5} + M_{7}</math>
: <math>C_{1,2} = M_{3} + M_{5}</math>
: <math>C_{2,1} = M_{2} + M_{4}</math>
: <math>C_{2,2} = M_{1} - M_{2} + M_{3} + M_{6}</math>
Für die Multiplikationen in der Berechnung der <math>M_i</math> wird obiges Verfahren [[Rekursion|rekursiv]] ausgeführt, bis das Problem auf die [[Multiplikation]] von [[Skalar (Mathematik)|Skalar]]en 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).

[[Datei:Strassen algorithm.svg|mini|800px|zentriert|Die linke Spalte repräsentiert eine <math>2\times 2</math>-[[Matrix (Mathematik)#Matrizenmultiplikation|Matrizenmultiplikation]]. Jede andere Spalte repräsentiert eine der <math>7</math> Multiplikationen des Strassen-Algorithmus.]]

== Aufwand ==
Der [[Matrizenmultiplikation#Standardalgorithmus|Standardalgorithmus zur Matrizenmultiplikation]] benötigt
: <math>n^{\log_{2}8}= n^3</math>
Multiplikationen der Elemente des Ringes <math>R</math>. Die benötigten Additionen sind hierbei nicht in die [[Komplexität (Informatik)|Komplexitätsberechnung]] eingeflossen, Sie können, abhängig von <math>R</math>, in Computerimplementationen viel schneller sein als die Multiplikationen. (Insbesondere bei gewöhnlichen ganzen oder Fließkommazahlen ist das oft der Fall.) Mit dem Strassen-Algorithmus wird die Anzahl der Multiplikationen auf
: <math>n^{\log_{2}7}\approx n^{2,807}</math>
reduziert. Die Reduktion der Anzahl der Multiplikationen führt allerdings zu einer Verringerung der [[Stabilität (Numerik)|numerischen Stabilität]].<ref>{{cite journal|last=Miller | first=Webb | title=Computational complexity and numerical stability | url=https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.9947&rep=rep1&type=pdf | language=en | year=1975 | journal=SIAM News | format=PDF | volume=4 | pages=97–107}}</ref>

Eine saubere Analyse einschließlich der Additionen ist mit dem Master-Theorem möglich: Die gewöhnliche Matrizenmultiplikation benötigt <math>2n^3-n^2 \in O(n^3)</math> Schritte (Multiplikationen und Additionen gleich gewichtet und zusammenaddiert). Dies gilt auch für den ganz oben erklärten naiven rekursiven Algorithmus, denn er erzeugt 8 Teilprobleme der Größe <math>\frac{n}{2}</math>und zudem sind 4 quadratische Matrizen der Seitenlänge <math>\frac{n}{2}</math> zu addieren, was einen zusätzlichen Aufwand von <math>4 \cdot \left( \frac{n}{2} \right)^2 = n^2</math> nach sich zieht, also gilt für seine Laufzeit die Rekursion

:<math>T(n) = 8 \cdot T \left( \frac{n}{2} \right) + n^2</math>

was nach dem [[Master-Theorem]] <math>T(n) \in O(n^{\log_2 8}) = O(n^3)</math> nach sich zieht.

Der Strassen-Algorithmus erzeugt hingegen jeweils nur sieben solche Teilprobleme, auch wenn dafür nun 18 Additionen oder Subtraktionen von Matrizen mit halber Seitenlänge, also <math>18 \cdot \left( \frac{n}{2} \right)^2 = \frac{9}{2} \cdot n^2</math> Additionen/Subtraktionen einzelner Matrixeinträge in <math>R</math>, erforderlich sind:

:<math>T(n) = 7 \cdot T \left( \frac{n}{2} \right) + \frac92 \cdot n^2</math>

Mit dem Master-Theorem folgt <math>T(n) \in O\left( n^{\log_2 7} \right)</math> (mit <math>\log_2 7 \approx 2{,}807</math>).

== Literatur ==
* Volker Strassen: ''Gaussian Elimination is not Optimal''. In: ''Numerische Mathematik'', Band 13, 1969, S. 354–356, {{ISSN|0029-599X}}, [[doi:10.1007/BF02165411]].

== Weblinks ==
* {{MathWorld |id=StrassenFormulas |title=Strassen Formulas}}

== Einzelnachweise ==
<references />

[[Kategorie:Numerische lineare Algebra]]
[[Kategorie:Algorithmus]]

Strassen-Algorithmus - Versionsgeschichte

2001:4BC9:803:190B:8ACF:8874:9911:A775: Es sollte stets O (groß Oh) stehen