Group-theoretic algorithms for matrix multiplication
arXiv:math/0511460 · doi:10.1109/SFCS.2005.39
Abstract
We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time use it to derive algorithms asymptotically faster than the standard algorithm. We describe several families of wreath product groups that achieve matrix multiplication exponent less than 3, the asymptotically fastest of which achieves exponent 2.41. We present two conjectures regarding specific improvements, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.
10 pages
References in corpus (1)
Cited by in corpus (39)
- Powers of Tensors and Fast Matrix Multiplication
- Fast linear algebra is stable
- On cap sets and the group-theoretic approach to matrix multiplication
- Fast matrix multiplication is stable
- The Growth Rate of Tri-Colored Sum-Free Sets
- LINVIEW: Incremental View Maintenance for Complex Analytical Queries
- Graph Expansion and Communication Costs of Fast Matrix Multiplication
- Fast Matrix Multiplication: Limitations of the Laser Method
- Faster Algorithms for Rectangular Matrix Multiplication
- Fast Feasible and Unfeasible Matrix Multiplication
- A New General-Purpose Method to Multiply 3x3 Matrices Using Only 23 Multiplications
- Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps
- Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
- Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
- Search and test algorithms for Triple Product Property triples
- Simple and Deterministic Matrix Sketching
- Strassen's Matrix Multiplication Algorithm for Matrices of Arbitrary Order
- Universal points in the asymptotic spectrum of tensors
- A Fast Search Algorithm for <m,m,m> Triple Product Property Triples and an Application for 5x5 Matrix Multiplication
- Matrix Multiplication, Trilinear Decompositions, APA Algorithms, and Summation
- Tensor and Matrix Inversions with Applications
- Sunflowers and Testing Triangle-Freeness of Functions
- Fast structured matrix computations: tensor rank and Cohn--Umans method
- Group-Theoretic Partial Matrix Multiplication
- Computational Complexity and Numerical Stability of Linear Problems
- Fast Approximate Matrix Multiplication by Solving Linear Systems
- Necklaces, Convolutions, and X+Y
- Kernels for time series with irregularly-spaced multivariate observations
- On Matrix Multiplication and Polynomial Identity Testing
- Chapter 10: Algebraic Algorithms
- Geometry and the complexity of matrix multiplication
- Group-theoretic Methods for Bounding the Exponent of Matrix Multiplication
- Upgrading Subgroup Triple Product Property Triples
- A new quadratic-time number-theoretic algorithm to solve matrix multiplication problem
- Errata and Addenda to Mathematical Constants
- Larger Corner-Free Sets from Combinatorial Degenerations
- The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
- Product-free subsets of groups, then and now
- Bounds for Bilinear Complexity of Noncommutative Group Algebras