Difference between revisions of "Strassen algorithm"
Borishaase (talk | contribs) |
Borishaase (talk | contribs) m (Strassen algorithm for a square matrix) |
||
| Line 1: | Line 1: | ||
'''Strassen algorithm for a symmetric matrix:''' | '''Strassen algorithm for a symmetric matrix:''' | ||
| − | 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> | + | For a square [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where sufficiently big <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> roughly halves that of the original algorithm in <math>\mathcal{O}(n^{(_2 7)})</math>. |
'''Proof:''' For <math>A := | '''Proof:''' For <math>A := | ||
| Line 13: | Line 13: | ||
\end{pmatrix}</math>. | \end{pmatrix}</math>. | ||
| − | The | + | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields the claim because of the halvings above (see top right).<math>\square</math> |
== See also == | == See also == | ||
Latest revision as of 15:39, 29 September 2023
Strassen algorithm for a symmetric matrix:
For a square matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where sufficiently big [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] roughly halves 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{ 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].
The geometric series yields the claim because of the halvings above (see top right).[math]\displaystyle{ \square }[/math]