Coppersmith–Winograd algorithm

In the mathematical discipline of linear algebra, the Coppersmith-Winograd algorithm is the fastest currently known algorithm for square matrix multiplication. It can multiply two ${\displaystyle n\times n}$ matrices in ${\displaystyle O(n^{2.376})}$ time. This is an improvement over the trivial ${\displaystyle O(n^{3})}$ time algorithm and the ${\displaystyle n^{2.807}}$ time Strassen algorithm. It might be possible to improve the exponent further; however, it has been shown that the exponent must be at least 2. The Coppersmith-Winograd algorithm is frequently used as building block in other algorithms to prove run time bounds, but it appears to be not particularly practical for implementations.

References

• Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251–280, 1990.