SU\G(𝔸)/K·U

Multiplying matrices faster than coppersmith-winograd

Authors

Virginia Vassilevska Williams
Type: Article
Publication Date: 2012-05-19
Citations: 930
DOI: https://doi.org/10.1145/2213977.2214056

Abstract

We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction. Using this approach we obtain a new improved bound on the matrix multiplication exponent ω<2.3727.

Locations

  • CiteSeer X (The Pennsylvania State University)
    View PDF

Ask a Question About This Paper

Summary

Login to see paper summary

Similar Works

Action Title Date Authors
+ PDF Ask
Fast Matrix Multiplication 2015-06-03 Andris Ambainis Yuval Filmus François Le Gall
+ PDF Ask
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method 2015-06-14 Andris Ambainis Yuval Filmus François Le Gall
+
Bounds on complexity of matrix multiplication away from Coppersmith–Winograd tensors 2022-05-13 Roser Homs Joachim Jelisiejew Mateusz Michałek Tim Seynnaeve
+ PDF Ask
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor 2018-01-01 François Le Gall Florent Urrutia
+ PDF Ask
Fast Matrix Multiplication: Limitations of the Laser Method 2014-11-20 Andris Ambainis Yuval Filmus François Le Gall
+ PDF Ask
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor 2017-08-18 François Le Gall Florent Urrutia
+ PDF Ask
Fast Matrix Multiplication: Limitations of the Laser Method 2014-01-01 Andris Ambainis Yuval Filmus
+ PDF Ask
Faster Matrix Multiplication via Asymmetric Hashing 2022-01-01 Ran Duan Hongxun Wu Renfei Zhou
+ PDF Ask
Faster Rectangular Matrix Multiplication by Combination Loss Analysis 2023-01-01 François Le Gall
+ PDF Ask
Barriers for rectangular matrix multiplication 2020-01-01 Matthias Christandl François Le Gall Vladimir Lysikov Jeroen Zuiddam
+
Barriers for rectangular matrix multiplication 2025-02-27 Matthias Christandl François Le Gall Vladimir Lysikov Jeroen Zuiddam
+ PDF Ask
Faster Rectangular Matrix Multiplication by Combination Loss Analysis 2024-01-01 François Le Gall
+
Matrix multiplication via arithmetic progressions 1990-03-01 Don Coppersmith S. Winograd
+ PDF Ask
Faster Matrix Multiplication via Asymmetric Hashing 2023-11-06 Ran Duan Hongxun Wu Renfei Zhou
+
Matrix multiplication via arithmetic progressions 1987-01-01 Don Coppersmith S. Winograd
+ PDF Ask
New Bounds for Matrix Multiplication: from Alpha to Omega 2024-01-01 Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou
+
Matrix Multiplication, a Little Faster 2020-01-15 Elaye Karstadt Oded Schwartz
+ PDF Ask
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication 2018-10-01 Josh Alman Virginia Vassilevska Williams
+ PDF Ask
Fast Feasible and Unfeasible Matrix Multiplication 2018-01-01 Victor Y. Pan
+
Practical fast matrix multiplication algorithms 2018-10-08 Jianyu Huang

Cited by (40)

Action Title Date Authors
+
Représentations des polynômes, algorithmes et bornes inférieures 2012-11-29 Bruno Grenet
+ PDF Ask
A framework for practical parallel fast matrix multiplication 2015-01-24 Austin R. Benson Grey Ballard
+
Nearly Linear Row Sampling Algorithm for Quantile Regression 2020-06-15 Yi Li Ruosong Wang Lin F. Yang Hanrui Zhang
+ PDF Ask
Solving Linear Programs in the Current Matrix Multiplication Time 2021-01-05 Michael B. Cohen Yin Tat Lee Zhao Song
+ PDF Ask
Quantum Algorithms for Matrix Products over Semirings 2017-01-01 François Le Gall Harumichi Nishimura
+ PDF Ask
Symmetries of matrix multiplication algorithms. I 2015-01-01 V. P. Burichenko
+ PDF Ask
Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits 2019-01-01 Enric Boix-Adserà Lior Eldar Saeed Mehraban
+ PDF Ask
Sketches of a platypus: persistent homology and its algebraic foundations 2012-01-01 Mikael Vejdemo‐Johansson
+
Representative Families of Product Families 2017-03-13 Fedor V. Fomin Daniel Lokshtanov Fahad Panolan Saket Saurabh
+ PDF Ask
Counting Subgraphs in Degenerate Graphs 2022-03-30 Suman K. Bera Lior Gishboliner Yevgeny Levanzov C. Seshadhri A. Shapira
+ PDF Ask
Which groups are amenable to proving exponent two for matrix multiplication? 2017-01-01 Jonah Blasiak Thomas M. Church Henry Cohn Joshua A. Grochow Chris Umans
+ PDF Ask
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles 2019-04-07 Mina Dalirrooyfard Thuy Duong Vuong Virginia Vassilevska Williams
+
Fast Bilinear Algorithms for Symmetric Tensor Contractions 2020-02-05 Edgar Solomonik James Demmel
+ PDF Ask
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH) 2020-01-01 Ray Li
+ PDF Ask
Solving Linear Programs with Sqrt(rank) Linear System Solves 2019-01-01 Yin Tat Lee Aaron Sidford
+ PDF Ask
On the Complexity of the F5 Gröbner basis Algorithm 2013-01-01 Magali Bardet Jean‐Charles Faugère Bruno Salvy
+ PDF Ask
Accelerating Sparse Approximate Matrix Multiplication on GPUs 2021-03-24 Xiaoyan Liu Yi Liu Ming Dun Bohong Yin Hailong Yang Zhongzhi Luan Depei Qian
+ PDF Ask
Algebraic properties of Heilbronn's exponential sum: supercharacters, Fermat congruences, and Heath-Brown's bound 2013-12-04 Stephan Ramon Garcia Mark Huber Bob Lutz
+ PDF Ask
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor 2018-01-01 François Le Gall Florent Urrutia
+
Into the Square: On the Complexity of Some Quadratic-time Solvable Problems 2016-04-01 Michele Borassi Pierluigi Crescenzi Michel Habib
+ PDF Ask
Computing the Gromov hyperbolicity of a discrete metric space 2015-02-12 Hervé Fournier Anas Ismail Antoine Vigneron
+
On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation 2013-01-23 Yann Strozecki
+
Fast matrix multiplication using coherent configurations 2013-01-06 Henry Cohn Christopher Umans
+ PDF Ask
Sparse sketches with small inversion bias 2020-11-21 Michał Dereziński Zhenyu Liao Edgar Dobriban Michael W. Mahoney
+ PDF Ask
Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems 2014-01-01 Daniel A. Spielman Shang‐Hua Teng
+ PDF Ask
Improved algorithms for exact and approximate boolean matrix decomposition 2015-10-01 Yuan Sun Shiwei Ye Yi Sun Tsunehiko Kameda
+ PDF Ask
Quasi-optimal Multiplication of Linear Differential Operators 2012-10-01 Alexandre Benoît Alin Bostan Joris van der Hoeven
+ PDF Ask
Computing the Gromov hyperbolicity of a discrete metric space 2012-10-11 Hervé Fournier Anas Ismail Antoine Vigneron
+ PDF Ask
Towards a geometric approach to Strassen’s asymptotic rank conjecture 2020-02-10 Austin Conner Fulvio Gesmundo J. M. Landsberg Emanuele Ventura Yao Wang
+ PDF Ask
A supercharacter approach to Heilbronn sums 2013-12-04 Stephan Ramon Garcia Bob Lutz
+ PDF Ask
On Computing the Hamiltonian Index of Graphs ⋆ 2022-01-01 Geevarghese Philip M. R. Rani R. Subashini
+ PDF Ask
Numerical CP decomposition of some difficult tensors 2016-12-16 Petr Tichavský Anh Huy Phan Andrzej Cichocki
+
TR-2012008: Randomized Matrix Computations III 2012-01-01 Victor Y. Pan Guoliang Qian Ai-Long Zheng
+
TR-2012006: Randomized Matrix Computations II 2012-01-01 Victor Y. Pan Guoliang Qian Ai-Long Zheng
+ PDF Ask
Fast Approximate Matrix Multiplication by Solving Linear Systems 2014-08-19 Shiva Manne Manjish Pal
+
An algorithmic hypergraph regularity lemma 2016-01-10 Brendan Nagle Vojtěch Rödl Mathias Schacht
+
Implementation Analysis of Strassen-Like Matrix Multiplication Algorithms Based on Block Decomposition 2019-03-11 Chongchong Liu
+
Fast Approximate Matrix Multiplication by Solving Linear Systems 2014-08-19 Shiva Manne Manjish Pal
+ PDF Ask
LU-Cholesky QR algorithms for thin QR decomposition 2019-10-25 Takeshi Terao Katsuhisa Ozaki Takeshi Ogita
+
Constant delay enumeration for conjunctive queries 2020-02-24 Christoph Berkholz Fabian Gerhardt Nicole Schweikardt

Citing (10)

Action Title Date Authors
+
Relative bilinear complexity and matrix multiplication. 1987-03-01 Volker Strassen
+
Matrix multiplication via arithmetic progressions 1990-03-01 Don Coppersmith S. Winograd
+
O(n2.7799) complexity for n × n approximate matrix multiplication 1979-06-01 Dario A. Bini Milvio Capovani Francesco Romani G. Lotti
+
On Sets of Integers Which Contain No Three Terms in Arithmetical Progression 1946-12-01 Felix Behrend
+
Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication 1982-05-01 Francesco Romani
+ PDF Ask
On Sunflowers and Matrix Multiplication 2012-06-01 Noga Alon Amir Shpilka Christopher Umans
+
Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations 1978-10-01 Victor Y. Pan
+ PDF Ask
A group-theoretic approach to fast matrix multiplication 2004-03-01 Henry Cohn Chris Umans
+
On Sunflowers and Matrix Multiplication. 2011-01-01 Noga Alon Amir Shpilka Christopher Umans
+ PDF Ask
Group-theoretic Algorithms for Matrix Multiplication 2005-11-15 Henry Cohn Robert Kleinberg Balázs Szegedy Chris Umans