Bemerkung:
Die Multiplikation zweier
-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
Matrizen rekursiv multipliziert werden
(mit 7 rekursiven Multiplikationen).
Komplexität:
Die Matrixmultiplikation nach Strassen benötigt (gemäß Master-Theorem) die Zeit
.