next up previous contents
Nächste Seite: Der Vier-Russen-Algorithmus Aufwärts: Transitive Hülle Vorherige Seite: Algorithmus von Warshall   Inhalt

Matrixmultiplikation nach Strassen

Bemerkung:
Die Multiplikation zweier $ 2 \times 2$-Matrizen erfordert 8 Multiplikationen und 4 Additionen. Die lässt sich jedoch umstellen, so dass 7 Multiplikationen und 18 Additionen erforderlich sind.

Algorithmus:
Die Matrixmultiplikation nach Strassen unterteilt beide Matrizen in je vier Blöcke, die analog $ 2 \times 2$ Matrizen rekursiv multipliziert werden (mit 7 rekursiven Multiplikationen).

$ \begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{pmatrix}
\begin{p...
...trix}
=
\begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{pmatrix}$

Komplexität:
Die Matrixmultiplikation nach Strassen benötigt (gemäß Master-Theorem) die Zeit $ O(n^{\log 7}) = O(n^{2.81})$.



2003-10-08