Matrix multiplication via arithmetic progressions
Don Coppersmith, Shmuel Winograd · 1987
We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.
Cited by 632 works. doi:10.1145/28395.28396 Open-access PDF
Authors
References
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On the Asymptotic Complexity of Matrix Multiplication
- Partial and Total Matrix Multiplication
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- How to Multiply Matrices Faster
- The asymptotic spectrum of tensors and the exponent of matrix multiplication
- On the asymptotic complexity of matrix multiplication
- Relative bilinear complexity and matrix multiplication.
- Asymptotic Complexity of Matrix Multiplication