Strassen-Algorithmus: Unterschied zwischen den Versionen

Aus MWiki
Wechseln zu: Navigation, Suche
K (Strassen-Algorithmus)
(Strassen-Algorithmus)
Zeile 6: Zeile 6:
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   A_{11} & A_{12} \\
 
   A_{11} & A_{12} \\
−
   A_{12} & A_{22}
+
   A_{12}^T & A_{22}
 
   \end{pmatrix}</math> gilt <math>A^TA =
 
   \end{pmatrix}</math> gilt <math>A^TA =
 
   \begin{pmatrix}
 
   \begin{pmatrix}
−
   A_{11}^TA_{11}+A_{12}^TA_{12} & A_{11}^TA_{12}+A_{12}^TA_{22} \\
+
   A_{11}A_{11}+A_{12}A_{12}^T & A_{11}A_{12}+A_{12}A_{22} \\
−
   A_{12}^TA_{11}+A_{22}^TA_{12} & A_{12}^TA_{12}+A_{22}^TA_{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>.
 
\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>.
  
Zeile 28: Zeile 28:
 
   A_{12}^TA_{11}+A_{22}^TA_{21} & A_{12}^TA_{12}+A_{22}^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>
 
\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 symmetrische Matrizen:'''
 
−
 
−
Für zwei symmetrische Matrizen <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>.
 
−
 
−
'''Beweis:''' Mit <math>B :=
 
−
  \begin{pmatrix}
 
−
  B_{11} & B_{12} \\
 
−
  B_{12} & B_{22}
 
−
  \end{pmatrix}</math> gilt <math>A^TB =
 
−
  \begin{pmatrix}
 
−
  A_{11}^TB_{11}+A_{12}^TB_{12} & A_{11}^TB_{12}+A_{12}^TB_{22} \\
 
−
  A_{12}^TB_{11}+A_{22}^TB_{12} & A_{12}^TB_{12}+A_{22}^TB_{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>
 
−
 
−
'''Neuer Algorithmus für eine symmetrische Matrix:'''
 
−
 
−
Für eine symmetrische Matrix <math>A \in \mathbb{C}^{n \times n}</math> mit <math>n \in \mathbb{N}^*</math> beträgt die Laufzeit <math>T_p(n)</math> des neuen Algorithmus für das Matrixprodukt <math>A^2</math> nach analoger Rechnung wie oben circa <math>3/7</math> von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)}).\square</math>
 
−
 
−
'''Neuer Algorithmus für eine quadratrische Matrix:'''
 
−
 
−
Für eine quadratrische Matrix <math>A \in \mathbb{C}^{n \times n}</math> mit <math>n \in \mathbb{N}^*</math> beträgt die Laufzeit <math>T_r(n)</math> des neuen Algorithmus für das Matrixprodukt <math>A^TA</math> circa <math>24/49</math> von der des Originalalgorithmus in <math>\mathcal{O}(n^{(_2 7)}).\square</math>
 
  
 
== Siehe auch ==
 
== Siehe auch ==

Version vom 22. März 2022, 06:47 Uhr

Strassen-Algorithmus für eine symmetrische Matrix:

Für eine symmetrische Matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] mit [math]\displaystyle{ n \in \mathbb{N}^* }[/math] beträgt die Laufzeit [math]\displaystyle{ T_s(n) }[/math] des Strassen-Algorithmus für das Matrixprodukt [math]\displaystyle{ A^2 }[/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_{12}^T & A_{22} \end{pmatrix} }[/math] gilt [math]\displaystyle{ 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]\displaystyle{ T_s(2n) = 3T_s(n) + 2n^{(_2 7)} }[/math]. Also [math]\displaystyle{ T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)} }[/math] bzw. [math]\displaystyle{ T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)} }[/math].

Die geometrische Reihe liefert wegen [math]\displaystyle{ T_s(1) = 1 }[/math]: [math]\displaystyle{ 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]\displaystyle{ = 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:

Für eine quadratrische Matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] mit [math]\displaystyle{ n \in \mathbb{N}^* }[/math] beträgt die Laufzeit [math]\displaystyle{ T_q(n) }[/math] des Strassen-Algorithmus für das Matrixprodukt [math]\displaystyle{ A^TA }[/math] circa [math]\displaystyle{ 4/7 }[/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}^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]\displaystyle{ T_q(2n) = 4T_s(n) + 2n^{(_2 7)} }[/math] bzw. [math]\displaystyle{ T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)}.\square }[/math]

Siehe auch

Liste mathematischer Symbole

Abgerufen von „https://de.mwiki.de/index.php?title=Strassen-Algorithmus&oldid=216“