Strassen-Algorithmus: Unterschied zwischen den Versionen
K (Strassen-Algorithmus für eine quadratrische Matrix) |
|||
| Zeile 1: | Zeile 1: | ||
'''Strassen-Algorithmus für eine quadratrische Matrix:''' | '''Strassen-Algorithmus für eine quadratrische Matrix:''' | ||
| − | Für eine quadratrische [[w:Matrix (Mathematik)|<span class="wikipedia">Matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> mit <math>2^k := n, k \in \mathbb{N}^*</math> beträgt die [[w:Laufzeit (Informatik)|<span class="wikipedia">Laufzeit</span>]] <math>T_q(n)</math> des [[w:Strassen-Algorithmus|<span class="wikipedia">Strassen-Algorithmus</span>]] für das [[w:Matrizenmultiplikation|<span class="wikipedia">Matrixprodukt</span>]] <math>AA^T</math> circa | + | Für eine quadratrische [[w:Matrix (Mathematik)|<span class="wikipedia">Matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> mit hinreichend großem <math>2^k := n, k \in \mathbb{N}^*</math> beträgt die [[w:Laufzeit (Informatik)|<span class="wikipedia">Laufzeit</span>]] <math>T_q(n)</math> des [[w:Strassen-Algorithmus|<span class="wikipedia">Strassen-Algorithmus</span>]] für das [[w:Matrizenmultiplikation|<span class="wikipedia">Matrixprodukt</span>]] <math>AA^T</math> circa die Hälfte von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)})</math>. |
'''Beweis:''' Mit <math>A := | '''Beweis:''' Mit <math>A := | ||
| Zeile 13: | Zeile 13: | ||
\end{pmatrix}</math>. | \end{pmatrix}</math>. | ||
| − | + | Die [[w:geometrische Reihe|<span class="wikipedia">geometrische Reihe</span>]] liefert die Behauptung wegen der obigen Halbierungen (s. oben rechts).\square</math> | |
== Siehe auch == | == Siehe auch == | ||
Aktuelle Version vom 29. September 2023, 15:33 Uhr
Strassen-Algorithmus für eine quadratrische Matrix:
Für eine quadratrische Matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] mit hinreichend großem [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 die Hälfte 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{ 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} }[/math].
Die geometrische Reihe liefert die Behauptung wegen der obigen Halbierungen (s. oben rechts).\square</math>