Difference between revisions of "Strassen algorithm"
Borishaase (talk | contribs) |
Borishaase (talk | contribs) m (Theorem for the Strassen algorithm) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | === 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 | ||
| − | + | <div style="text-align:center;"><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> | + | \end{pmatrix}</math> as well as <math>AA^T = |
\begin{pmatrix} | \begin{pmatrix} | ||
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}</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]