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 $n\times n$ matrices in $O(n^{2.376})$ time. This is an improvement over the trivial $O(n^{3})$ time algorithm and the $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.