On the asymptotic complexity of matrix multiplication
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The main results of this paper have the following flavor: given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that ω ≪ 2.495364.Keywords
This publication has 5 references indexed in Scilit:
- On the Asymptotic Complexity of Matrix MultiplicationSIAM Journal on Computing, 1982
- Partial and Total Matrix MultiplicationSIAM Journal on Computing, 1981
- Relations between exact and approximate bilinear algorithms. ApplicationsCalcolo, 1980
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear FormsSIAM Journal on Computing, 1973
- Gaussian elimination is not optimalNumerische Mathematik, 1969