Matrix Multiplication via Arithmetic Progressions

Matrix Multiplication via Arithmetic Progressions

1987 | Don Coppersmith and Shmuel Winograd
The paper presents a new method for accelerating matrix multiplication asymptotically, building on recent ideas by Volker Strassen. The authors use a basic trilinear form that is not a matrix product and novelly apply the Salem-Spencer Theorem, which provides a dense set of integers with no three-term arithmetic progression. By hashing the indices of the blocks of variables to integers and setting to zero any block whose indices do not map into the Salem-Spencer set, they ensure that products of nonzero variables in the trilinear form form arithmetic progressions. This allows them to reduce the problem to several disjoint matrix products, leading to an exponent of 2.376. The paper also includes a simpler construction with an exponent of 2.404 and a more complex version yielding an exponent of 2.388. The authors discuss the implications of Strassen's approach for proving that the matrix exponent ω equals 2 and highlight the need for a characteristic two analogue of the Salem-Spencer theorem to extend their techniques to a larger class of basic algorithms.The paper presents a new method for accelerating matrix multiplication asymptotically, building on recent ideas by Volker Strassen. The authors use a basic trilinear form that is not a matrix product and novelly apply the Salem-Spencer Theorem, which provides a dense set of integers with no three-term arithmetic progression. By hashing the indices of the blocks of variables to integers and setting to zero any block whose indices do not map into the Salem-Spencer set, they ensure that products of nonzero variables in the trilinear form form arithmetic progressions. This allows them to reduce the problem to several disjoint matrix products, leading to an exponent of 2.376. The paper also includes a simpler construction with an exponent of 2.404 and a more complex version yielding an exponent of 2.388. The authors discuss the implications of Strassen's approach for proving that the matrix exponent ω equals 2 and highlight the need for a characteristic two analogue of the Salem-Spencer theorem to extend their techniques to a larger class of basic algorithms.
Reach us at info@study.space