Strassen-Algorithmus: Unterschied zwischen den Versionen
K (Satz zum Strassen-Algorithmus) |
K (Satz zum Strassen-Algorithmus) |
||
| (3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | + | === Satz zum Strassen-Algorithmus === | |
| − | Die originale [[w:Laufzeit (Informatik)|<span class="wikipedia">Laufzeit</span>]] <math>T(n) = \mathcal{O}(n^{(_2 7)})</math> des [[w:Strassen-Algorithmus|<span class="wikipedia">Strassen-Algorithmus</span>]] | + | Die originale [[w:Laufzeit (Informatik)|<span class="wikipedia">Laufzeit</span>]] <math>T(n) = \mathcal{O}(n^{(_2 7)})</math> des [[w:Strassen-Algorithmus|<span class="wikipedia">Strassen-Algorithmus</span>]] verkürzt sich zur Berechnung des [[w:Matrizenmultiplikation|<span class="wikipedia">Matrixprodukts</span>]] <math>AA^T</math> ca. um <math>\tilde{3}</math> für hinreichend großes <math>n := 2^k, k \in \mathbb{N}^*</math> und die [[w:Matrix (Mathematik)|<span class="wikipedia">Matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> aufgrund der [[w:geometrische Reihe|<span class="wikipedia">geometrischen Reihe</span>]] und |
<div style="text-align:center;"><math>A := | <div style="text-align:center;"><math>A := | ||
| 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 == | ||
| Zeile 17: | Zeile 17: | ||
[[Kategorie:Teilgebiet der Mathematik]] | [[Kategorie:Teilgebiet der Mathematik]] | ||
| − | [[en: | + | [[en:Strassen algorithm]] |
Aktuelle Version vom 28. September 2024, 02:44 Uhr
Satz zum Strassen-Algorithmus
Die originale Laufzeit [math]\displaystyle{ T(n) = \mathcal{O}(n^{(_2 7)}) }[/math] des Strassen-Algorithmus verkürzt 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]