Ran Raz
ABSTRACT
We prove a lower bound of Ω(m2 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 doesn't use products with field elements of absolute value larger than 1 (where mxm is the size of each matrix). That is, our lower bound is super-linear 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. More generally, for any c = c(m) ρ 1, we obtain a lower bound of Ω(m2 log2c 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 doesn't use products with field elements of absolute value larger than c. We also prove size-depth tradeoffs for such circuits.
- N. Alon, J.H. Spencer and P.Erdos. The Probabiliatic Method. John Wiley and Sons, Inc., 1992.Google Scholar
- M. Bläser. A 2.5n lower bound for the rank of n x n matrix multiplication over arbitrary fields. In 40th IEEE Symposium on Foundations of Computer Science, pages 45--50, 1999. Google ScholarDigital Library
- N.H. Bshouty. A lower bound for matrix multiplication. SIAM Journal on Computing, 18:759--765, 1989. Google ScholarDigital Library
- B. Chazelle. A spectral approach to lower bounds with applications to geometric searching. SIAM Journal on Computing, 27:545--556, 1998. Google ScholarDigital Library
- D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9:251--280, 1990. Google ScholarDigital Library
- J.V.Z. Gathen. Algebraic complexity theory. Ann. Rev. Computer Science, 1988, pages 317--347. Google ScholarDigital Library
- S. Geman. A limit theorem for the norm of random matrices. Annals of Probability, 8:252--261, 1980.Google ScholarCross Ref
- G.H. Golub and C.F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1983.Google Scholar
- A.J. Hoffman and H.W. Wielandt. The variation of the spectrum of normal matrices. Duke (MATH)ematical Journal 20:37--39, 1953.Google Scholar
- S.V. Lokam. Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In 36th IEEE Symposium on Foundations of Computer Science, pages 6--15, 1995. Google ScholarDigital Library
- J. Morgenstern. Note on a lower bound of the linear complexity of the fast fourier transform. JACM, 20(2): 305--306, 1973. Google ScholarDigital Library
- N. Nissan and A. Wigderson. On the complexity of bilinear forms. In 27th ACM Symposium on Theory of Computing, pages 723--732, 1995. Google ScholarDigital Library
- P. Pudlak. A note on using the detrminant for proving lower bounds on the size of linear circuits. Electronic Colloquium on Computational Complexity (ECCC), Report No. 42, 1998.Google Scholar
- R. Raz and A. Shpilka. Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. In 33rd ACM Symposium on Theory of Computing, pages 409--418, 2001. Google ScholarDigital Library
- A. Shpilka. Lower bounds for matrix product. In 42nd IEEE Symposium on Foundations of Computer Science, 2001. Google ScholarDigital Library
- J.W. Silverstein. The smallest eigenvalue of a large dimensional Wishart matrix. Annals of Probability, 13:1364--1368, 1985.Google ScholarCross Ref
- V. Strassen. Gaussian elimination is not optimal. Numer. (MATH), 13:354--356, 1969.Google Scholar
Index Terms
- On the complexity of matrix product
Recommendations
On the Complexity of Matrix Product
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 ...
Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product
The error complexity analysis of three algorithms for matrix multiplication and matrix chain product has been given. It is shown that the usual inner product type algorithm is by far the best algorithm for simple matrix multiplication or matrix chain ...
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth ...
Comments