Difference between revisions of "Strassen algorithm"
Borishaase (talk | contribs) (Strassen algorithm) |
Borishaase (talk | contribs) (Strassen algorithm) |
||
Line 1: | Line 1: | ||
'''Strassen algorithm for a symmetric matrix:''' | '''Strassen algorithm for a symmetric matrix:''' | ||
− | For a [[w: | + | For a square [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where <math>2^k := n, k \in \mathbb{N}^*</math>, the [[w:Runtime (program lifecycle phase)|<span class="wikipedia">runtime</span>]] <math>T_q(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>AA^T</math> is about <math>2/3</math> that of the original algorithm in <math>\mathcal{O}(n^{(_2 7)})</math>. |
'''Proof:''' For <math>A := | '''Proof:''' For <math>A := | ||
\begin{pmatrix} | \begin{pmatrix} | ||
A_{11} & A_{12} \\ | A_{11} & A_{12} \\ | ||
− | A_{ | + | A_{21} & A_{22} |
\end{pmatrix}</math>, it holds that <math>A^TA = | \end{pmatrix}</math>, it holds that <math>A^TA = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
− | A_{11}A_{11}+A_{12}A_{12}^T & A_{11}A_{ | + | 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> and <math> | + | \end{pmatrix}</math> and <math>T_q(2n) = 4T_q(n) + 2n^{(_2 7)}</math> or <math>T_q(n) = 4T_q(n/2) + 2/7n^{(_2 7)}</math>. |
− | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields because of <math> | + | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields because of <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> |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== See also == | == See also == |
Revision as of 03:33, 1 April 2023
Strassen algorithm for a symmetric matrix:
For a square matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ 2^k := n, k \in \mathbb{N}^* }[/math], the runtime [math]\displaystyle{ T_q(n) }[/math] of the Strassen algorithm for the matrix product [math]\displaystyle{ AA^T }[/math] is about [math]\displaystyle{ 2/3 }[/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}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] and [math]\displaystyle{ T_q(2n) = 4T_q(n) + 2n^{(_2 7)} }[/math] or [math]\displaystyle{ T_q(n) = 4T_q(n/2) + 2/7n^{(_2 7)} }[/math].
The geometric series yields because of [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]