Difference between revisions of "Strassen algorithm"
Borishaase (talk | contribs) (Strassen algorithm) |
Borishaase (talk | contribs) |
||
| Line 11: | Line 11: | ||
A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ | 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 | A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T | ||
| − | \end{pmatrix | + | \end{pmatrix}</math>. |
| − | The | + | The rate of usual matrix multiplications is <math>2/3.\square</math> |
== See also == | == See also == | ||
Revision as of 04:29, 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].
The rate of usual matrix multiplications is [math]\displaystyle{ 2/3.\square }[/math]