On the complexity of matrix product

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of matrix product

Full text

Pdf (202 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 3B table of contents

Pages: 144 - 151

Year of Publication: 2002

ISBN:1-58113-495-9

Author

Ran Raz

Weizmann Institute, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 65, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.509932 What is a DOI?

ABSTRACT

We prove a lower bound of &OHgr;(m² 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) &rhoe; 1, we obtain a lower bound of &OHgr;(m² 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon, J.H. Spencer and P.Erdos. The Probabiliatic Method. John Wiley and Sons, Inc., 1992.
	2	Markus Bläser, A - Lower Bound for the Rank of - Matrix Multiplication over Arbitrary Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.45, October 17-18, 1999
	3	Nader H. Bshouty, A lower bound for matrix multiplication, SIAM Journal on Computing, v.18 n.4, p.759-765, Aug. 1989 [doi>10.1137/0218052]
	4	Bernard Chazelle, A Spectral Approach to Lower Bounds with Applications to Geometric Searching, SIAM Journal on Computing, v.27 n.2, p.545-556, April 1998 [doi>10.1137/S0097539794275665]
	5	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	6	Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	7	S. Geman. A limit theorem for the norm of random matrices. Annals of Probability, 8:252--261, 1980.
	8	G.H. Golub and C.F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1983.
	9	A.J. Hoffman and H.W. Wielandt. The variation of the spectrum of normal matrices. Duke (MATH)ematical Journal 20:37--39, 1953.
	10	S. V. Lokam, Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.6, October 23-25, 1995
	11	Jacques Morgenstern, Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform, Journal of the ACM (JACM), v.20 n.2, p.305-306, April 1973 [doi>10.1145/321752.321761]
	12	Noam Nisan , Avi Wigderson, On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.723-732, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225290]
	13	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.
	14	Ran Raz , Amir Shpilka, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.409-418, July 2001, Hersonissos, Greece [doi>10.1145/380752.380833]
	15	A. Shpilka, Lower Bounds for Matrix Product, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.358, October 14-17, 2001
	16	J.W. Silverstein. The smallest eigenvalue of a large dimensional Wishart matrix. Annals of Probability, 13:1364--1368, 1985.
	17	V. Strassen. Gaussian elimination is not optimal. Numer. (MATH), 13:354--356, 1969.

CITED BY 2

	Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, Foundations and Trends® in Theoretical Computer Science, v.4 n.1–2, p.1-155, January 2009
	Peter Bürgisser , Martin Lotz, Lower bounds on the bounded coefficient complexity of bilinear maps, Journal of the ACM (JACM), v.51 n.3, p.464-482, May 2004