Difference between revisions of "Strassen algorithm"
Borishaase (talk | contribs) m (Straßen algoritm) |
Borishaase (talk | contribs) m (Straßen algorithm) |
||
Line 13: | Line 13: | ||
\end{pmatrix}</math> and <math>T_s(2n) = 3T_s(n) + 2n^{(_2 7)}</math>. Thus <math>T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)}</math> and <math>T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)}</math>. | \end{pmatrix}</math> and <math>T_s(2n) = 3T_s(n) + 2n^{(_2 7)}</math>. Thus <math>T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)}</math> and <math>T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)}</math>. | ||
− | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields because of <math>T_s(1) = 1</math>: <math>T_s(n) = 27T_s(n/8) + 2/7n^ | + | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields because of <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)})</math>.<math>\square</math> |
'''Strassen algorithm for a square matrix:''' | '''Strassen algorithm for a square matrix:''' |
Revision as of 04:20, 21 March 2022
Strassen algorithm for a symmetric matrix:
For a symmetric matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ n \in \mathbb{N}^* }[/math], the runtime [math]\displaystyle{ T_s(n) }[/math] of the Strassen algorithm for the matrix product [math]\displaystyle{ A^2 }[/math] is about half that of the original algorithm in [math]\displaystyle{ \mathcal{O}(n^{(_2 7)}) }[/math].
Proof: For [math]\displaystyle{ A := \begin{pmatrix} A_{11} & A_{12} \\ A_{12} & A_{22} \end{pmatrix} }[/math], it holds that [math]\displaystyle{ A^TA = \begin{pmatrix} A_{11}^TA_{11}+A_{12}^TA_{12} & A_{11}^TA_{12}+A_{12}^TA_{22} \\ A_{12}^TA_{11}+A_{22}^TA_{12} & A_{12}^TA_{12}+A_{22}^TA_{22} \end{pmatrix} }[/math] and [math]\displaystyle{ T_s(2n) = 3T_s(n) + 2n^{(_2 7)} }[/math]. Thus [math]\displaystyle{ T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)} }[/math] and [math]\displaystyle{ T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)} }[/math].
The geometric series yields because of [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)}) }[/math].[math]\displaystyle{ \square }[/math]
Strassen algorithm for a square matrix:
For a square matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ n \in \mathbb{N}^* }[/math], the runtime [math]\displaystyle{ T_q(n) }[/math] of the Strassen algorithm for the matrix product [math]\displaystyle{ A^TA }[/math] is about [math]\displaystyle{ 4/7 }[/math] that of the original algorithm in [math]\displaystyle{ \mathcal{O}(n^{(_2 7)}) }[/math].
Proof: For [math]\displaystyle{ A := \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} }[/math], it holds that [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] such that [math]\displaystyle{ T_q(2n) = 4T_s(n) + 2n^{(_2 7)} }[/math] and [math]\displaystyle{ T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)} }[/math].[math]\displaystyle{ \square }[/math]