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, the exponent must be at least 2 (because an ${\displaystyle n\times n}$ matrix has ${\displaystyle n^{2}}$ values, and all of them have to be read at least once to calculate the exact result). The Coppersmith-Winograd algorithm is frequently used as building block in other algorithms to prove theoretical time bounds, but it appears to be not particularly practical for implementations.

A newer approach by Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans gets the exponent 2.41 via a group-theoretic approach.

References

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

External links

• Article by Cohn/Kleinberg/Szegedy/Umans