Strassen-Algorithmus
Strassen-Algorithmus für eine quadratrische Matrix:
Für eine quadratrische Matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] mit [math]\displaystyle{ 2^k := n, k \in \mathbb{N}^* }[/math] beträgt die Laufzeit [math]\displaystyle{ T_q(n) }[/math] des Strassen-Algorithmus für das Matrixprodukt [math]\displaystyle{ AA^T }[/math] circa [math]\displaystyle{ 2/3 }[/math] von der des Originalalgorithmus in [math]\displaystyle{ \mathcal{O}(n^{(_2 7)}) }[/math].
Beweis: Mit [math]\displaystyle{ A := \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} }[/math] gilt [math]\displaystyle{ A^TA = \begin{pmatrix} A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T \end{pmatrix} }[/math].
Der Anteil gewöhnlicher Matrixmultiplikationen (oben rechts) ist [math]\displaystyle{ 2/3.\square }[/math]