D. Coppersmith
ABSTRACT
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.
- Beh.F. A. Behrend, "On sets of integers whidh contain no three terms in arithmetical progression," Proc. Nnt. Acad. Sci. USA 32 (1946) 331-332; MR 8, 317.Google Scholar
Cross Ref
- CW.D. Coppersmith and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication," SIAM Journal on Computing, Vol. 11, No. 3, August 1982, pp. 472-492.Google ScholarCross Ref
- Pan.V. Pan, "tlow to Multiply Matrices Faster," Springer t~:cture Notes in Computer Science, vol 179, Google ScholarDigital Library
- Sch.A. Sch~nhage, "Partial and 'l'otal Matrix Multiplicalion," SIAM J. on Computing, 10, 3, 434-456.Google ScholarCross Ref
- SS.R. Salem and D. C. Spencer, "On sets of integers which contain no three terms in arithmetical progression," ?roc. Nat. Acad. Sci. USA 28 (1942) 561-563.Google ScholarCross Ref
- Str.V. Strassen, "The Asymptotic Spectrum of 1'ensors and the Exponent of Matrix Multiplication," 1986 FOCS, pp. 49-54; also "Relative bilinear complexity and mat:fix multiplication," preprint.Google Scholar
Index Terms
- Matrix multiplication via arithmetic progressions
Recommendations
Fast sparse matrix multiplication
Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m0.7n1.2+n2+o(1)) algebraic operations (i.e., multiplications, additions ...
Matrix multiplication via arithmetic progressions
Special issue on computational algebraic complexityWe present a new method for accelerating matrix multiplication asymptotically. Thiswork 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 ...
Generalized matrix inversion is not harder than matrix multiplication
Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given ...
Comments