A Lower Bound for Matrix Multiplication
Author:
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (4) , 759-765
Abstract
This paper proves that computing the product of two $n \times n$ matrices over the binary field requires at least $2.5n^2 - o(n^2 )$ multiplications.
Keywords
This publication has 17 references indexed in Scilit:
- A lower bound for polynomial multiplicationTheoretical Computer Science, 1985
- Improved lower bounds for some matrix multiplication problemsInformation Processing Letters, 1985
- On the Multiplicative Complexity of Modules over Associative AlgebrasSIAM Journal on Computing, 1985
- On the complexity of multiplication in finite fieldsTheoretical Computer Science, 1983
- On the algorithmic complexity of associative algebrasTheoretical Computer Science, 1981
- On the Complexity of Bilinear Forms with CommutativitySIAM Journal on Computing, 1980
- An Improved Lower Bound on Polynomial MultiplicationIEEE Transactions on Computers, 1980
- On the optimal evaluation of a set of bilinear formsLinear Algebra and its Applications, 1978
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear FormsSIAM Journal on Computing, 1973
- On Minimizing the Number of Multiplications Necessary for Matrix MultiplicationSIAM Journal on Applied Mathematics, 1971