research-article

Powers of tensors and fast matrix multiplication

Author:

François Le GallAuthors Info & Claims

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Pages 296 - 303

https://doi.org/10.1145/2608628.2608664

Published: 23 July 2014 Publication History

Abstract

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computation, 1990] and obtain the upper bound ω < 2.3728639 on the exponent of square matrix multiplication, which slightly improves the best known upper bound.

References

[1]

N. Alon, A. Shpilka, and C. Umans. On sunflowers and matrix multiplication. Computational Complexity, 22(2):219--243, 2013.

[2]

A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization. SIAM, 2001.

Digital Library

[3]

M. Bläser. Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013.

[4]

S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.

Digital Library

[5]

P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory. Springer, 1997.

Digital Library

[6]

H. Cohn, R. D. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 379--388, 2005.

Digital Library

[7]

H. Cohn and C. Umans. Fast matrix multiplication using coherent configurations. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1074--1087, 2013.

Digital Library

[8]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251--280, 1990.

Digital Library

[9]

A. M. Davie and A. J. Stothers. Improved bound for complexity of matrix multiplication. Proceedings of the Royal Society of Edinburgh, 143A:351--370, 2013.

[10]

S.-C. Fang and J. H.-S. Tsao. Entropy optimization: interior point methods. In Encyclopedia of Optimization, pages 544--548. Springer, 2001.

[11]

Y. Filmus. Matrix multiplication I and II, 2014. Lecture notes available at http://www.cs.toronto.edu/~yuvalf/.

[12]

F. Le Gall. Faster algorithms for rectangular matrix multiplication. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 514--523, 2012.

Digital Library

[13]

A. Schönhage. Partial and total matrix multiplication. SIAM Journal on Computing, 10(3):434--455, 1981.

[14]

A. Stothers. On the Complexity of Matrix Multiplication. PhD thesis, University of Edinburgh, 2010.

[15]

V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.

Digital Library

[16]

V. Strassen. The asymptotic spectrum of tensors and the exponent of matrix multiplication. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, pages 49--54, 1986.

Digital Library

[17]

V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th ACM Symposium on Theory of Computing, pages 887--898, 2012. Most recent version available at the author's homepage.

Digital Library

Cited By

Kansal MSharma VSharma PJäntschi L(2024)A Globally Convergent Iterative Method for Matrix Sign Function and Its Application for Determining the Eigenvalues of a Matrix PencilSymmetry10.3390/sym1604048116:4(481)Online publication date: 16-Apr-2024
https://doi.org/10.3390/sym16040481
Zhao HFan AOuyang XKoutris P(2024)Conjunctive Queries with Negation and Aggregation: A Linear Time CharacterizationProceedings of the ACM on Management of Data10.1145/36511382:2(1-19)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651138
Dey DGupta MMohar BShinkar IO'Donnell R(2024)Nearly Optimal Fault Tolerant Distance OracleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649697(944-955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649697
Show More Cited By

Index Terms

Powers of tensors and fast matrix multiplication

Recommendations

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n^2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm ...
Fast sparse matrix multiplication

Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m^0.7n^1.2+n^2+o(1)) algebraic operations (i.e., multiplications, additions ...
Geometric rank of tensors and subrank of matrix multiplication
CCC '20: Proceedings of the 35th Computational Complexity Conference

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

July 2014

444 pages

ISBN:9781450325011

DOI:10.1145/2608628

Editor:
Katsusuke Nabeshima
The University of Tokushima, Japan
,
General Chairs:
Kosaku Nagasaka
Kobe University, Japan
,
Franz Winkler
RISC, University Linz, Austria
,
Program Chair:
Agnes Szanto
North Carolina State University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSAC '14

ISSAC '14: International Symposium on Symbolic and Algebraic Computation

July 23 - 25, 2014

Kobe, Japan

Acceptance Rates

ISSAC '14 Paper Acceptance Rate 51 of 96 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

567
Total Citations
View Citations
1,293
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kansal MSharma VSharma PJäntschi L(2024)A Globally Convergent Iterative Method for Matrix Sign Function and Its Application for Determining the Eigenvalues of a Matrix PencilSymmetry10.3390/sym1604048116:4(481)Online publication date: 16-Apr-2024
https://doi.org/10.3390/sym16040481
Zhao HFan AOuyang XKoutris P(2024)Conjunctive Queries with Negation and Aggregation: A Linear Time CharacterizationProceedings of the ACM on Management of Data10.1145/36511382:2(1-19)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651138
Dey DGupta MMohar BShinkar IO'Donnell R(2024)Nearly Optimal Fault Tolerant Distance OracleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649697(944-955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649697
Björklund AKaski PMohar BShinkar IO'Donnell R(2024)The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both TrueProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649656(859-870)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649656
Liu TKuang JNiu X(2024)An Iterative Method for the Distance Constraints in a Multi-Sensor Positioning SystemIEEE Transactions on Vehicular Technology10.1109/TVT.2023.331963673:2(2728-2739)Online publication date: Feb-2024
https://doi.org/10.1109/TVT.2023.3319636
Eshkiki HMora BXie X(2024)Fully Connected Networks on a Diet With the Mediterranean Matrix MultiplicationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.317619735:1(634-647)Online publication date: Jan-2024
https://doi.org/10.1109/TNNLS.2022.3176197
Zhang KWang SLai XWang LGuan JHu BShi T(2024)Impossible Differential Cryptanalysis and a Security Evaluation Framework for AND-RX CiphersIEEE Transactions on Information Theory10.1109/TIT.2023.329224170:8(6025-6040)Online publication date: Aug-2024
https://doi.org/10.1109/TIT.2023.3292241
Tian CYu JMeng PZhang GTian WZhang Y(2024)How to Securely and Efficiently Solve the Large-Scale Modular System of Linear Equations on the CloudIEEE Transactions on Cloud Computing10.1109/TCC.2024.340824012:3(913-927)Online publication date: Jul-2024
https://doi.org/10.1109/TCC.2024.3408240
Schwartz OToledo SVaknin NWiernik G(2024)Alternative Basis Matrix Multiplication is Fast and Stable2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00013(38-51)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00013
Nissim RSchwartz O(2024)Revisiting “Rapid multiplication of rectangular matrices”Research in Mathematics10.1080/27684830.2024.238833411:1Online publication date: 19-Aug-2024
https://doi.org/10.1080/27684830.2024.2388334
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents