|
|
| (16 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| − | '''Strassen-Algorithmus für eine symmetrische Matrix:'''
| |
| − |
| |
| − | Für eine [[w:Symmetrische Matrix|<span class="wikipedia">symmetrische Matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> mit <math>n \in \mathbb{N}^*</math> beträgt die [[w:Laufzeit (Informatik)|<span class="wikipedia">Laufzeit</span>]] <math>T_s(n)</math> des [[w:Strassen-Algorithmus|<span class="wikipedia">Strassen-Algorithmus</span>]] für das [[w:Matrizenmultiplikation|<span class="wikipedia">Matrixprodukt</span>]] <math>A^2</math> circa die Hälfte von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)})</math>.
| |
| − |
| |
| − | '''Beweis:''' Mit <math>A :=
| |
| − | \begin{pmatrix}
| |
| − | A_{11} & A_{12} \\
| |
| − | A_{12}^T & A_{22}
| |
| − | \end{pmatrix}</math> gilt <math>A^TA =
| |
| − | \begin{pmatrix}
| |
| − | A_{11}A_{11}+A_{12}A_{12}^T & A_{11}A_{12}+A_{12}A_{22} \\
| |
| − | A_{12}^TA_{11}+A_{22}A_{12}^T & A_{12}^TA_{12}+A_{22}A_{22}
| |
| − | \end{pmatrix}</math> und <math>T_s(2n) = 3T_s(n) + 2n^{(_2 7)}</math>. Also <math>T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)}</math> bzw. <math>T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)}</math>.
| |
| − |
| |
| − | Die [[w:Geometrische Reihe|<span class="wikipedia">geometrische Reihe</span>]] liefert wegen <math>T_s(1) = 1</math>: <math>T_s(n) = 27T_s(n/8) + 2/7n^{(_2 7)}(1+3/7 + (3/7)^2 + ...) = 3^{(_2n)} + 2/7n^{(_2 7)} (1-(3/7)^{(_2n)})/(1-3/7)</math> <math>= n^{(_2 3)} + \hat{2}(n^{(_2 7)}-n^{(_2 3)}) = \hat{2} (n^{(_2 3)} + n^{(_2 7)}).\square</math>
| |
| − |
| |
| | '''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>n \in \mathbb{N}^*</math> beträgt die Laufzeit <math>T_q(n)</math> des Strassen-Algorithmus für das Matrixprodukt <math>A^TA</math> circa <math>4/7</math> von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)})</math>. | + | 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 23: |
Zeile 7: |
| | A_{11} & A_{12} \\ | | A_{11} & A_{12} \\ |
| | A_{21} & A_{22} | | A_{21} & A_{22} |
| − | \end{pmatrix}</math> gilt <math>A^TA = | + | \end{pmatrix}</math> gilt <math>AA^T = |
| − | \begin{pmatrix}
| |
| − | A_{11}^TA_{11}+A_{21}^TA_{21} & A_{11}^TA_{12}+A_{21}^TA_{22} \\
| |
| − | A_{12}^TA_{11}+A_{22}^TA_{21} & A_{12}^TA_{12}+A_{22}^TA_{22}
| |
| − | \end{pmatrix}</math> und <math>T_q(2n) = 4T_s(n) + 2n^{(_2 7)}</math> bzw. <math>T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)}.\square</math>
| |
| − | | |
| − | '''Neuer Algorithmus für zwei quadratische Matrizen der folgenden Form:'''
| |
| − | | |
| − | Für zwei <math>A, B \in \mathbb{C}^{n \times n}</math> mit <math>n \in \mathbb{N}^*</math> beträgt die Laufzeit <math>T_z(n)</math> für das Matrixprodukt <math>AB</math> des neuen Algorithmus circa <math>6/7</math> von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)})</math>, wenn <math>A</math> ebenfalls die nachfolgende Form von <math>B</math> hat:
| |
| − | | |
| − | '''Beweis:''' Mit <math>B :=
| |
| | \begin{pmatrix} | | \begin{pmatrix} |
| − | B_{11} & B_{12} \\ | + | A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ |
| − | B_{12} & B_{22}
| + | A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T |
| − | \end{pmatrix}</math> gilt <math>AB =
| + | \end{pmatrix}</math>. |
| − | \begin{pmatrix}
| |
| − | A_{11}B_{11}+A_{12}B_{12} & A_{11}B_{12}+A_{12}B_{22} \\
| |
| − | A_{12}B_{11}+A_{22}B_{12} & A_{12}B_{12}+A_{22}B_{22} | |
| − | \end{pmatrix} =: C</math>. Wird | |
| − | | |
| − | : <math>M_{1} := A_{12} \cdot (B_{11} + B_{12})</math>
| |
| − | : <math>M_{2} := A_{12} \cdot (B_{12} + B_{22})</math>
| |
| − | : <math>M_{3} := A_{22} \cdot (B_{12} + B_{22})</math>
| |
| − | : <math>M_{4} := (A_{12} - A_{11})\cdot B_{11}</math>
| |
| − | : <math>M_{5} := (A_{12} - A_{11})\cdot B_{12}</math>
| |
| − | : <math>M_{6} := (A_{12} - A_{22})\cdot B_{22}</math>
| |
| − | | |
| − | gesetzt, so gilt
| |
| − | | |
| − | : <math>C_{11} = M_{1} - M_{4}</math>
| |
| − | : <math>C_{12} = M_{2} - M_{5}</math>
| |
| − | : <math>C_{21} = M_{1} - M_{2} + M_{3} + M_{6}</math>
| |
| − | : <math>C_{22} = M_{2} - M_{6} .\square</math>
| |
| − | | |
| − | '''Bemerkung:''' Haben die Zerlegungen von <math>A</math> und <math>B</math> wieder die angegebene Form, ist die Laufzeit sogar <math>\mathcal{O}(n^{(_2 6)})</math>.
| |
| − | | |
| − | == Siehe auch ==
| |
| − | [[Liste mathematischer Symbole]]
| |
| − | [[Kategorie:Teilgebiet der Mathematik]]
| |
| | | | |
| − | [[en:Strassen algorithm]] | + | 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 == |
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>
Siehe auch
Liste mathematischer Symbole