Strassen algorithm

Strassen algorithm for a symmetric matrix:

For a symmetric matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ n \in \mathbb{N}^* }[/math], the runtime [math]\displaystyle{ T_s(n) }[/math] of the Strassen algorithm for the matrix product [math]\displaystyle{ A^2 }[/math] is about half 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_{12}^T & A_{22} \end{pmatrix} }[/math], it holds that [math]\displaystyle{ 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]\displaystyle{ T_s(2n) = 3T_s(n) + 2n^{(_2 7)} }[/math]. Thus [math]\displaystyle{ T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)} }[/math] and [math]\displaystyle{ T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)} }[/math].

The geometric series yields because of [math]\displaystyle{ T_s(1) = 1 }[/math]: [math]\displaystyle{ 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]\displaystyle{ = n^{(_2 3)} + \hat{2}(n^{(_2 7)}-n^{(_2 3)}) = \hat{2} (n^{(_2 3)} + n^{(_2 7)}) }[/math].[math]\displaystyle{ \square }[/math]

Strassen algorithm for a square matrix:

For a square matrix [math]\displaystyle{ A \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ n \in \mathbb{N}^* }[/math], the runtime [math]\displaystyle{ T_q(n) }[/math] of the Strassen algorithm is for the matrix product [math]\displaystyle{ A^TA }[/math] about [math]\displaystyle{ 4/7 }[/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}^TA_{11}+A_{21}^TA_{21} & A_{11}^TA_{12}+A_{21}^TA_{22} \\ A_{12}^TA_{11}+A_{22}^TA_{21} & A_{12}^TA_{12}+A_{22}^TA_{22} \end{pmatrix} }[/math] such that [math]\displaystyle{ T_q(2n) = 4T_s(n) + 2n^{(_2 7)} }[/math] and [math]\displaystyle{ T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)} }[/math].[math]\displaystyle{ \square }[/math]

New algorithm for two square matrices of the following form:

For two [math]\displaystyle{ A, B \in \mathbb{C}^{n \times n} }[/math] where [math]\displaystyle{ n \in \mathbb{N}^* }[/math], the runtime is [math]\displaystyle{ T_z(n) }[/math] for the matrix product [math]\displaystyle{ AB }[/math] of the new algorithm about [math]\displaystyle{ 6/7 }[/math] that of the original algorithm in [math]\displaystyle{ \mathcal{O}(n^{(_2 7)}) }[/math] if [math]\displaystyle{ A }[/math] has the following form of [math]\displaystyle{ B }[/math], too:

Proof: For [math]\displaystyle{ B := \begin{pmatrix} B_{11} & B_{12} \\ B_{12} & B_{22} \end{pmatrix} }[/math], it holds that [math]\displaystyle{ AB = \begin{pmatrix} A_{11}B_{11}+A_{12}B_{12} & A_{11}B_{12}+A_{12}B_{22} \\ A_{12}B_{11}+A_{22}B_{12} & A_{12}B_{12}+A_{22}B_{22} \end{pmatrix} =: C }[/math]. Putting

[math]\displaystyle{ M_{1} := A_{12} \cdot (B_{11} + B_{12}) }[/math]

[math]\displaystyle{ M_{2} := A_{12} \cdot (B_{12} + B_{22}) }[/math]

[math]\displaystyle{ M_{3} := A_{22} \cdot (B_{12} + B_{22}) }[/math]

[math]\displaystyle{ M_{4} := (A_{11} - A_{12})\cdot B_{11} }[/math]

[math]\displaystyle{ M_{5} := (A_{11} - A_{12})\cdot B_{12} }[/math]

[math]\displaystyle{ M_{6} := (A_{12} - A_{22})\cdot B_{22} }[/math]

implies

[math]\displaystyle{ C_{11} = M_{1} + M_{4} }[/math]

[math]\displaystyle{ C_{12} = M_{2} + M_{5} }[/math]

[math]\displaystyle{ C_{21} = M_{1} - C_{22} + M_{3} }[/math]

[math]\displaystyle{ C_{22} = M_{2} - M_{6} . }[/math]

This is also true if [math]\displaystyle{ A }[/math] has the following form of [math]\displaystyle{ B }[/math]:

For [math]\displaystyle{ B := \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{11} \end{pmatrix} }[/math], it holds that [math]\displaystyle{ AB = \begin{pmatrix} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{11} \\ A_{21}B_{11}+A_{11}B_{21} & A_{21}B_{12}+A_{11}B_{11} \end{pmatrix} =: C }[/math]. Putting

[math]\displaystyle{ M_{1} := A_{11} \cdot (B_{11} + B_{12}) }[/math]

[math]\displaystyle{ M_{2} := A_{21} \cdot (B_{11} + B_{12}) }[/math]

[math]\displaystyle{ M_{3} := A_{12} \cdot (B_{11} - B_{21}) }[/math]

[math]\displaystyle{ M_{4} := (A_{11} - A_{12})\cdot B_{11} }[/math]

[math]\displaystyle{ M_{5} := (A_{11} - A_{21})\cdot B_{11} }[/math]

[math]\displaystyle{ M_{6} := (A_{11} + A_{12})\cdot B_{21} }[/math]

implies

[math]\displaystyle{ C_{11} = M_{3} + M_{4} }[/math]

[math]\displaystyle{ C_{12} = M_{1} - M_{4} }[/math]

[math]\displaystyle{ C_{21} = C_{11} - M_{5} + M_{6} }[/math]

[math]\displaystyle{ C_{22} = M_{2} + M_{5} .\square }[/math]

Remark: If the compounds of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are again of the forms mentioned, the runtime is even [math]\displaystyle{ \mathcal{O}(n^{(_2 6)}) }[/math].

See also

List of mathematical symbols