Strassen-Algorithmus: Unterschied zwischen den Versionen
(Satz zum Strassen-Algorithmus) |
(→Satz zum Strassen-Algorithmus) |
||
| Zeile 11: | Zeile 11: | ||
A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ | 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 | A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T | ||
| − | \end{pmatrix}\square</math> | + | \end{pmatrix}.\square</math></div> |
== Siehe auch == | == Siehe auch == | ||
Version vom 28. September 2024, 02:21 Uhr
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]