Matrix multiplication via arithmetic progressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Matrix multiplication via arithmetic progressions

Full text

Pdf (476 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 1 - 6

Year of Publication: 1987

ISBN:0-89791-221-7

Authors

D. Coppersmith	Department of Mathematical Sciences, IBM Thomas J Watson Research Center, P O Box 218, Yorktown Heights, New York
S. Winograd	Department of Mathematical Sciences, IBM Thomas J Watson Research Center, P O Box 218, Yorktown Heights, New York

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 53, Downloads (12 Months): 427, Citation Count: 64

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/28395.28396 What is a DOI?

ABSTRACT

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.

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.

	Beh	F. A. Behrend, "On sets of integers whidh contain no three terms in arithmetical progression," Proc. Nnt. Acad. Sci. USA 32 (1946) 331-332; MR 8, 317.
	CW	D. Coppersmith and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication," SIAM Journal on Computing, Vol. 11, No. 3, August 1982, pp. 472-492.
	Pan	Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, 1984
	Sch	A. Sch~nhage, "Partial and 'l'otal Matrix Multiplicalion," SIAM J. on Computing, 10, 3, 434-456.
	SS	R. Salem and D. C. Spencer, "On sets of integers which contain no three terms in arithmetical progression," ?roc. Nat. Acad. Sci. USA 28 (1942) 561-563.
	Str	V. Strassen, "The Asymptotic Spectrum of 1'ensors and the Exponent of Matrix Multiplication," 1986 FOCS, pp. 49-54; also "Relative bilinear complexity and mat:fix multiplication," preprint.

CITED BY 64

	Lillian Lee, Fast context-free grammar parsing requires fast boolean matrix multiplication, Journal of the ACM (JACM), v.49 n.1, p.1-15, January 2002
	M.-Y. Kao , P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.181-192, May 13-17, 1990, Baltimore, Maryland, United States
	J. Ullman , M. Yannakakis, High-probability parallel transitive closure algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.200-209, July 02-06, 1990, Island of Crete, Greece
	Nicholas J. Higham, Exploiting fast matrix multiplication within the level 3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.352-368, Dec. 1990
	B. Ravikumar, A note on checking matrix products (extended abstract), Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.937-943, March 1992, Kansas City, Missouri, United States
	G. Villard, Computing Popov and Hermite forms of polynomial matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.250-258, July 24-26, 1996, Zurich, Switzerland
	Takeshi Tokuyama , Jun Nakano, Geometric algorithms for a minimum cost assignment problem, Proceedings of the seventh annual symposium on Computational geometry, p.262-271, June 10-12, 1991, North Conway, New Hampshire, United States
	Qingshan Luo , John B. Drake, A scalable parallel Strassen's matrix multiplication algorithm for distributed-memory computers, Proceedings of the 1995 ACM symposium on Applied computing, p.221-226, February 26-28, 1995, Nashville, Tennessee, United States
	Sha Guo , Wei Sun , Mark A. Weiss, Solving satisfiability and implication problems in database systems, ACM Transactions on Database Systems (TODS), v.21 n.2, p.270-293, June 1996
	Håkan Jakobsson, Mixed-approach algorithms for transitive closure (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.199-205, May 29-31, 1991, Denver, Colorado, United States
	Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.14-21, July 15-17, 1991, Bonn, West Germany
	S. Ar , M. Blum , B. Codenotti , P. Gemmell, Checking approximate computations over the reals, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.786-795, May 16-18, 1993, San Diego, California, United States
	Tze-heng Ma , Jeremy Spinrad, An O(n2) time algorithm for the 2-chain cover problem and related problems, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.363-372, January 28-30, 1991, San Francisco, California, United States
	Joseph Cheriyan , John H. Reif, Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.335-344, September 1992, Orlando, Florida, United States
	A. Aggarwal , R. J. Anderson , M.-Y. Kao, Parallel depth-first search in general directed graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.297-308, May 14-17, 1989, Seattle, Washington, United States
	Jeffrey D. Ullman , Mihalis Yannakakis, The input/output complexity of transitive closure, ACM SIGMOD Record, v.19 n.2, p.44-53, Jun. 1990
	Thomas H. Spencer, Time-work tradeoffs for parallel algorithms, Journal of the ACM (JACM), v.44 n.5, p.742-778, Sept. 1997
	W. Sun , M. A. Weiss, An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.997-1001, December 1994
	D. H. Bailey , H. R. P. Gerguson, A Strassen-Newton algorithm for high-speed parallelizable matrix inversion, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.419-424, November 12-17, 1988, Orlando, Florida, United States
	Daniel N. Rockmore, Efficient computation of Fourier inversion for finite groups, Journal of the ACM (JACM), v.41 n.1, p.31-66, Jan. 1994
	Weifa Liang , Richard P. Brent , Hong Shen, Fully Dynamic Maintenance of k-Connectivity in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.12 n.8, p.846-864, August 2001
	Joseph Bates , Alon Lavie, Recognizing substrings of LR(k) languages in linear time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.1051-1077, May 1994
	J. Stephens , V. Raghavan, On Single-Fault Set Diagnosability in the PMC Model, IEEE Transactions on Computers, v.42 n.8, p.981-983, August 1993
	Michael A. Bender , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Finding least common ancestors in directed acyclic graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.845-854, January 07-09, 2001, Washington, D.C., United States
	Elchanan Mossel , Ryan O'Donnell , Rocco P. Servedio, Learning juntas, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	David Bruce Wilson , James Gary Propp, How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 28-30, 1996, Atlanta, Georgia, United States
	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States
	Elaine M. Eschen , Jeremy P. Sinrad, An O(n2 algorithm for circular-arc graph recognition, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.128-137, January 25-27, 1993, Austin, Texas, United States
	Daniele V. Finocchiaro , Marco Pellegrini, On computing the diameter of a point set in high dimensional Euclidean space, Theoretical Computer Science, v.287 n.2, p.501-514, 28 September 2002
	Olaf Hall-Holt , Matthew J. Katz , Piyush Kumar , Joseph S. B. Mitchell , Arik Sityon, Finding large sticks and potatoes in polygons, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.474-483, January 22-26, 2006, Miami, Florida
	Brent Gregory , Erich Kaltofen, Analysis of the binary complexity of asymptotically fast algorithms for linear system solving, ACM SIGSAM Bulletin, v.22 n.2, p.41-49, April 1988
	Toshihiro Fujito , Takashi Doi, A 2-approximation NC algorithm for connected vertex cover and tree cover, Information Processing Letters, v.90 n.2, p.59-63, 30 April 2004
	Erich Kaltofen , Gilles Villard, Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, v.162 n.1, p.133-146, 1 January 2004
	Wang Lian , David Wai-lok Cheung , Nikos Mamoulis , Siu-Ming Yiu, An Efficient and Scalable Algorithm for Clustering XML Documents by Structure, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.82-96, January 2004
	M.-Y. Kao , G. E. Shannon, Local reorientation, global order, and planar topology, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.286-296, May 14-17, 1989, Seattle, Washington, United States
	Michael A. Bender , Martín Farach-Colton , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, v.57 n.2, p.75-94, November 2005
	David Saunders , Zhendong Wan, Smith normal form of dense integer matrices fast algorithms into practice, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.274-281, July 04-07, 2004, Santander, Spain
	Sanguthevar Rajasekaran , Shibu Yooseph, TAL recognition in O(M(n²)) time, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.166-173, June 26-30, 1995, Cambridge, Massachusetts
	Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning functions of k relevant variables, Journal of Computer and System Sciences, v.69 n.3, p.421-434, November 2004
	Victor Chepoi , Feodor Dragan, Finding a central vertex in an HHD-free graph, Discrete Applied Mathematics, v.131 n.1, p.93-111, 6 September 2003
	Piotr Sankowski, Processor efficient parallel matching, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Feodor F. Dragan, Estimating all pairs shortest paths in restricted graph families: a unified approach, Journal of Algorithms, v.57 n.1, p.1-21, September 2005
	Qing Hu , Xiaojun Shen , Weifa Liang, Optimally Routing LC Permutations on k-Extra-Stage Cube-Type Networks, IEEE Transactions on Computers, v.45 n.1, p.97-103, January 1996
	Candelaria Hernández Goya , Pino Caballero Gil, Using average case intractability in cryptography, Proceedings of the 4th WSEAS International Conference on Applied Informatics and Communications, p.1-5, December 17-19, 2004, Tenerife, Canary Islands, Spain
	Maria Patricia Dobson , Marisa Gutierrez , Michel Habib , Jayme L. Szwarcfiter, On transitive orientations with restricted covering graphs, Information Processing Letters, v.101 n.3, p.119-125, February, 2007
	Paolo D'Alberto , Alexandru Nicolau, Adaptive Strassen's matrix multiplication, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	Matthew J. Rattigan , Marc Maier , David Jensen, Graph clustering with network structure indices, Proceedings of the 24th international conference on Machine learning, p.783-790, June 20-24, 2007, Corvalis, Oregon
	Emmanuel Filiot , Joachim Niehren , Jean-Marc Talbot , Sophie Tison, Polynomial time fragments of XPath with variables, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	J. M. Lucas , M. G. Sackrowit, Efficient parallel algorithms for path problems in directed graphs, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.369-377, June 18-21, 1989, Santa Fe, New Mexico, United States
	R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States
	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States
	Shafi Goldwasser , Dan Gutfreund , Alexander Healy , Tali Kaufman , Guy N. Rothblum, A (de)constructive approach to program checking, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Warren J. Schudy, Finding strongly connected components in parallel using o(log²n) reachability queries, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Ran Duan , Seth Pettie, Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.384-391, January 04-06, 2009, New York, New York
	David B. Chandler , Maw-Shang Chang , Ton Kloks , Jiping Liu , Sheng-Lung Peng, Partitioned probe comparability graphs, Theoretical Computer Science, v.396 n.1-3, p.212-222, May, 2008
	Quan Hoang Nguyen , Bernhard Scholz, Computing SSA Form with Matrices, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.121-132, July, 2007
	Ignaz Rutter , Alexander Wolff, Computing large matchings fast, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.183-192, January 20-22, 2008, San Francisco, California
	Piotr Sankowski, Faster dynamic matchings and vertex connectivity, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.118-126, January 07-09, 2007, New Orleans, Louisiana
	Martin Albrecht, Algebraic Attacks on the Courtois Toy Cipher, Cryptologia, v.32 n.3, p.220-276, July 2008
	Edo Liberty , Steven W. Zucker, The Mailman algorithm: A note on matrix--vector multiplication, Information Processing Letters, v.109 n.3, p.179-182, January, 2009
	Isaac Elias , Jens Lagergren, Fast neighbor joining, Theoretical Computer Science, v.410 n.21-23, p.1993-2000, May, 2009
	Paolo D'Alberto , Alexandru Nicolau, Adaptive Winograd's matrix multiplications, ACM Transactions on Mathematical Software (TOMS), v.36 n.1, p.1-23, March 2009
	Rasmus Resen Amossen , Rasmus Pagh, Faster join-projects and sparse matrix multiplications, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Charalampos E. Tsourakakis , U. Kang , Gary L. Miller , Christos Faloutsos, DOULION: counting triangles in massive graphs with a coin, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France