Strassen-Algorithmus

Satz zum Strassen-Algorithmus

Die originale Laufzeit [math]\displaystyle{ T(n) = \mathcal{O}(n^{(_2 7)}) }[/math] des Strassen-Algorithmus reduziert sich zur Berechnung des Matrixprodukts [math]\displaystyle{ AA^T }[/math] ca. um [math]\displaystyle{ \tilde{3} }[/math] für hinreichend großes [math]\displaystyle{ n := 2^k, k \in \mathbb{N}^* }[/math] und die Matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] aufgrund der geometrischen Reihe und

[math]\displaystyle{ A := \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} }[/math] sowie [math]\displaystyle{ AA^T = \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}\square }[/math].

Siehe auch

Liste mathematischer Symbole