Matrix Multiplication via Arithmetic Progressions

Matrix Multiplication via Arithmetic Progressions

1987 | Don Coppersmith and Shmuel Winograd
Coppersmith and Winograd present a new method for accelerating matrix multiplication asymptotically, building on Strassen's ideas. They use a trilinear form not a matrix product and apply the Salem-Spencer theorem, which provides a dense set of integers with no three-term arithmetic progression. This leads to a matrix exponent of 2.376. The paper outlines the use of Schönhage's τ-theorem, Strassen's construction, and the Salem-Spencer theorem to derive the exponent. They show that by hashing block indices and zeroing certain blocks, they can ensure that nonzero blocks are used in at most one product, allowing the application of the τ-theorem. The paper details various constructions, including an easy case yielding 2.404 and a more complex case yielding 2.388. The full paper provides a general theory and a more complicated starting case leading to the final exponent of 2.376. The authors conclude that their approach allows for more efficient matrix multiplication algorithms and suggest further research into characteristic two analogues of the Salem-Spencer theorem.Coppersmith and Winograd present a new method for accelerating matrix multiplication asymptotically, building on Strassen's ideas. They use a trilinear form not a matrix product and apply the Salem-Spencer theorem, which provides a dense set of integers with no three-term arithmetic progression. This leads to a matrix exponent of 2.376. The paper outlines the use of Schönhage's τ-theorem, Strassen's construction, and the Salem-Spencer theorem to derive the exponent. They show that by hashing block indices and zeroing certain blocks, they can ensure that nonzero blocks are used in at most one product, allowing the application of the τ-theorem. The paper details various constructions, including an easy case yielding 2.404 and a more complex case yielding 2.388. The full paper provides a general theory and a more complicated starting case leading to the final exponent of 2.376. The authors conclude that their approach allows for more efficient matrix multiplication algorithms and suggest further research into characteristic two analogues of the Salem-Spencer theorem.
Reach us at info@study.space
[slides] Matrix multiplication via arithmetic progressions | StudySpace