Editing Strassen algorithm (section)

== Improvements to Strassen algorithm ==
{{Further information|Matrix multiplication algorithm#Sub-cubic algorithms|Computational complexity of matrix multiplication}}
It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:<ref>{{Cite journal |last=Winograd |first=S. |date=October 1971 |title=On multiplication of 2 × 2 matrices |url=https://linkinghub.elsevier.com/retrieve/pii/0024379571900097 |journal=Linear Algebra and Its Applications |language=en |volume=4 |issue=4 |pages=381–388 |doi=10.1016/0024-3795(71)90009-7}}</ref>

<math>
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
\begin{bmatrix}
A & C \\
B & D
\end{bmatrix}
=
\begin{bmatrix}
t + b{\color{red}\times}B & w + v + (a + b - c - d){\color{red}\times}D \\
w + u + d{\color{red}\times}(B + C - A - D) & w + u + v
\end{bmatrix}
</math>

where <math>t = a{\color{red}\times}A, \; u = (c - a){\color{red}\times}(C - D), \; v = (c + d){\color{red}\times}(C - A), \; w = t + (c + d - a){\color{red}\times}(A + D - C)</math>.

This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.{{sfnp|Knuth|1997|p=500}}

The algorithm was further optimised in 2017 using an alternative basis,<ref>{{Cite book |last1=Karstadt |first1=Elaye |last2=Schwartz |first2=Oded |chapter=Matrix Multiplication, a Little Faster |date=2017-07-24 |title=Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures |chapter-url=https://dl.acm.org/doi/10.1145/3087556.3087579 |language=en |publisher=ACM |pages=101–110 |doi=10.1145/3087556.3087579 |isbn=978-1-4503-4593-4}}</ref> reducing the number of matrix additions per bilinear step to 12 while maintaining the number of matrix multiplications, and again in 2023:<ref>{{Cite journal |last1=Schwartz |first1=Oded |last2=Vaknin |first2=Noa |date=2023-12-31 |title=Pebbling Game and Alternative Basis for High Performance Matrix Multiplication |url=https://epubs.siam.org/doi/10.1137/22M1502719 |journal=SIAM Journal on Scientific Computing |language=en |volume=45 |issue=6 |pages=C277–C303 |doi=10.1137/22M1502719 |bibcode=2023SJSC...45C.277S |issn=1064-8275|url-access=subscription }}</ref>

<math>
\begin{align}
A_{22} &= A_{12} - A_{21} + A_{22}; \\
B_{22} &= B_{12} - B_{21} + B_{22},
\end{align}
</math>

{{col-begin}}
{{col-break}}
<math>
\begin{align}
t_1 &= A_{21} + A_{22}; \\
t_2 &= A_{22} - A_{12}; \\
t_3 &= A_{22} - A_{11}; \\
t_4 &= B_{22} - B_{11}; \\
t_5 &= B_{21} + B_{22}; \\
t_6 &= B_{22} - B_{12},
\end{align}
</math>
{{col-break}}
<math>
\begin{align}
M_1 &= A_{11} {\color{red}\times} B_{11}; \\
M_2 &= A_{12} {\color{red}\times} B_{21}; \\
M_3 &= A_{21} {\color{red}\times} t_4; \\
M_4 &= A_{22} {\color{red}\times} B_{22}; \\
M_5 &= t_1 {\color{red}\times} t_5; \\
M_6 &= t_2 {\color{red}\times} t_6; \\
M_7 &= t_3 {\color{red}\times} B_{12},
\end{align}
</math>
{{col-break}}
<math>
\begin{align}
C_{11} &= M_1 + M_2; \\
C_{12} &= M_5 - M_7; \\
C_{21} &= M_3 + M_6; \\
C_{22} &= M_5 + M_6-M_2-M_4. \\
\end{align}
</math>
{{col-end}}
<math>
\begin{align}
C_{12} &= C_{12} - C_{22}; \\
C_{21} &= C_{22} - C_{21},
\end{align}
</math>