Difference between revisions of "Strassen algorithm"

From MWiki
Jump to: navigation, search
m (Strassen algorithm)
m (Theorem for the Strassen algorithm)
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
'''Strassen algorithm for a symmetric matrix:'''
+
=== Theorem for the Strassen algorithm ===
 +
Computing the [[w:Matrix multiplication|<span class="wikipedia">matrix product</span>]] <math>AA^T</math> shortens the original [[w:Execution_(computing)#Runtime|<span class="wikipedia">runtime</span>]] <math>T(n) = \mathcal{O}(n^{(_2 7)})</math> of the [[w:Strassen algorithm|<span class="wikipedia">Strassen algorithm</span>]] roughly by <math>\tilde{3}</math> for sufficiently big <math>n := 2^k, k \in \mathbb{N}^*</math> and the [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> due to the [[w:geometric series|<span class="wikipedia">geometric series</span>]] and
  
−
For a [[w:Symmetric matrix|<span class="wikipedia">symmetric matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where <math>n \in \mathbb{N}^*</math>, the [[w:Runtime (program lifecycle phase)|<span class="wikipedia">runtime</span>]] <math>T_s(n)</math> of the [[w:Strassen algorithm|<span class="wikipedia">Strassen algorithm</span>]] for the [[w:Matrix multiplication|<span class="wikipedia">matrix product</span>]] <math>A^2</math> is about half that of the original algorithm in <math>\mathcal{O}(n^{(_2 7)})</math>.
+
<div style="text-align:center;"><math>A :=  
−
 
 
−
'''Proof:''' For <math>A :=
 
−
  \begin{pmatrix}
 
−
  A_{11} & A_{12} \\
 
−
  A_{12}^T & A_{22}
 
−
  \end{pmatrix}</math>, it holds that <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> 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^{(_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:'''
 
−
 
 
−
For a square [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where <math>n \in \mathbb{N}^*</math>, the runtime <math>T_q(n)</math> of the Strassen algorithm is for the matrix product <math>A^TA</math> about <math>4/7</math> that of the original algorithm in  <math>\mathcal{O}(n^{(_2 7)})</math>.
 
−
 
 
−
'''Proof:''' For <math>A :=  
 
 
   \begin{pmatrix}
 
   \begin{pmatrix}
 
   A_{11} & A_{12} \\
 
   A_{11} & A_{12} \\
 
   A_{21} & A_{22}
 
   A_{21} & A_{22}
−
   \end{pmatrix}</math>, it holds that <math>A^TA =
+
   \end{pmatrix}</math> as well as <math>AA^T =
 
   \begin{pmatrix}
 
   \begin{pmatrix}
−
   A_{11}^TA_{11}+A_{21}^TA_{21} & A_{11}^TA_{12}+A_{21}^TA_{22} \\
+
   A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\
−
   A_{12}^TA_{11}+A_{22}^TA_{21} & A_{12}^TA_{12}+A_{22}^TA_{22}
+
   A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T
−
\end{pmatrix}</math> such that <math>T_q(2n) = 4T_s(n) + 2n^{(_2 7)}</math> and <math>T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)}</math>.<math>\square</math>
+
\end{pmatrix}.\square</math></div>
  
 
== See also ==
 
== See also ==

Latest revision as of 02:56, 28 September 2024

Theorem for the Strassen algorithm

Computing the matrix product [math]\displaystyle{ AA^T }[/math] shortens the original runtime [math]\displaystyle{ T(n) = \mathcal{O}(n^{(_2 7)}) }[/math] of the Strassen algorithm roughly by [math]\displaystyle{ \tilde{3} }[/math] for sufficiently big [math]\displaystyle{ n := 2^k, k \in \mathbb{N}^* }[/math] and the matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] due to the geometric series and

[math]\displaystyle{ A := \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} }[/math] as well as [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}.\square }[/math]

See also

List of mathematical symbols

Retrieved from "https://en.mwiki.de/index.php?title=Strassen_algorithm&oldid=362"