Strassen-Algorithmus: Unterschied zwischen den Versionen
(Strassen-Algorithmus) |
(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 Laufzeit <math>T_q(n)</math> des Strassen-Algorithmus für das Matrixprodukt <math> | + | 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 <math>2/3</math> von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)})</math>. |
'''Beweis:''' Mit <math>A := | '''Beweis:''' Mit <math>A := | ||
Zeile 25: | Zeile 9: | ||
\end{pmatrix}</math> gilt <math>A^TA = | \end{pmatrix}</math> gilt <math>A^TA = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
− | A_{11} | + | A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ |
− | A_{ | + | A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T |
− | \end{pmatrix}</math> und <math>T_q(2n) = | + | \end{pmatrix}</math> und <math>T_q(2n) = 4T_q(n) + 2n^{(_2 7)}</math> bzw. <math>T_q(n) = 4T_q(n/2) + 2/7(n)^{(_2 7)}</math>. |
+ | |||
+ | Die [[w:Geometrische Reihe|<span class="wikipedia">geometrische Reihe</span>]] liefert wegen <math>T_q(1) = 1</math>: <math>T_q(n) = 64T_q(n/8) + 2/7n^{(_2 7)}(1+4/7 + (4/7)^2 + ...) = 2/7n^{(_2 7)} (1-(4/7)^{(_2n)})/(1-4/7) = 2/3n^{(_2 7)}.\square</math> | ||
== Siehe auch == | == Siehe auch == |
Version vom 1. April 2023, 03:27 Uhr
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] und [math]\displaystyle{ T_q(2n) = 4T_q(n) + 2n^{(_2 7)} }[/math] bzw. [math]\displaystyle{ T_q(n) = 4T_q(n/2) + 2/7(n)^{(_2 7)} }[/math].
Die geometrische Reihe liefert wegen [math]\displaystyle{ T_q(1) = 1 }[/math]: [math]\displaystyle{ T_q(n) = 64T_q(n/8) + 2/7n^{(_2 7)}(1+4/7 + (4/7)^2 + ...) = 2/7n^{(_2 7)} (1-(4/7)^{(_2n)})/(1-4/7) = 2/3n^{(_2 7)}.\square }[/math]