On the Complexity of Matrix Product
Author:
- Ran RazRRRan Raz
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (5) , 1356-1369
Abstract
Our main result is a lower bound of $\Omega(m^2 \log m)$ for the size of any arithmetic circuit for the product of two matrices, over the real or complex numbers, as long as the circuit does not use products with field elements of absolute value larger than 1 (where m × m is the size of each matrix). That is, our lower bound is superlinear in the number of inputs and is applied for circuits that use addition gates, product gates, and products with field elements of absolute value up to 1. We also prove size-depth tradeoffs for such circuits: We show that if a circuit, as above, is of depth d, then its size is $\Omega(m^{2+ 1/O(d)})$.
Keywords
This publication has 12 references indexed in Scilit:
- Lower bounds for matrix product2001
- A Spectral Approach to Lower Bounds with Applications to Geometric SearchingSIAM Journal on Computing, 1998
- On the complexity of bilinear forms1995
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- A Lower Bound for Matrix MultiplicationSIAM Journal on Computing, 1989
- The Smallest Eigenvalue of a Large Dimensional Wishart MatrixThe Annals of Probability, 1985
- A Limit Theorem for the Norm of Random MatricesThe Annals of Probability, 1980
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier TransformJournal of the ACM, 1973
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- The variation of the spectrum of a normal matrixDuke Mathematical Journal, 1953