Powers of Tensors and Fast Matrix Multiplication

Abstract

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic constructions 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 $\omega <2.3728639$ on the exponent of square matrix multiplication, which slightly improves the best known upper bound.

28 pages

Cited by in corpus (78)

• On cap sets and the group-theoretic approach to matrix multiplication
• Fast Algorithms for Convolutional Neural Networks
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• Faster Dynamic Matrix Inverse for Faster LPs
• Fast likelihood evaluation for multivariate phylogenetic comparative methods: the PCMBase R package
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Quantum Algorithms to Matrix Multiplication
• Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
• Solving Linear Programs in the Current Matrix Multiplication Time
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• Computing Canonical Bases of Modules of Univariate Relations
• Fast Feasible and Unfeasible Matrix Multiplication
• A Fast Algorithm for Computing the p-Curvature
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Dimensionality reduction of SDPs through sketching
• Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
• Graph Matching with Partially-Correct Seeds
• Equimatchable Claw-Free Graphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Fast simulation of planar Clifford circuits
• WavmatND: A MATLAB Package for Non-Decimated Wavelet Transform and its Applications
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
• Multivariate Newton Interpolation
• Matrix multiplication algorithms from group orbits
• Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability
• Solving the clique cover problem on (bull, $C_4$)-free graphs
• Quantum algorithms for shortest paths problems in structured instances
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
• On the Quest for an Acyclic Graph
• A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation
• Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets
• Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
• Fair Marketplace for Secure Outsourced Computations
• On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
• Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity
• An Illuminating Algorithm for the Light Bulb Problem
• Finding Even Cycles Faster via Capped k-Walks
• Improving the numerical stability of fast matrix multiplication
• Faster Sparse Multivariate Polynomial Interpolation of Straight-Line Programs
• Faster Algorithms for Multivariate Interpolation with Multiplicities and Simultaneous Polynomial Approximations
• Random Projection in Deep Neural Networks
• Fast Approximate Matrix Multiplication by Solving Linear Systems
• The border support rank of two-by-two matrix multiplication is seven
• How Hard is it to Find (Honest) Witnesses?
• On Solving Linear Systems in Sublinear Time
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
• Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
• Gradient-based Data Subversion Attack Against Binary Classifiers
• How proofs are prepared at Camelot
• Faster Dynamic Range Mode
• Improved Algorithms for Exact and Approximate Boolean Matrix Decomposition
• Designing Strassen's algorithm
• All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier
• A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case
• Graph Matching via convex relaxation to the simplex
• Simple, Fast and Practicable Algorithms for Cholesky, LU and QR Decomposition Using Fast Rectangular Matrix Multiplication
• Bayesian Inference Gaussian Process Multiproxy Alignment of Continuous Signals (BIGMACS): Applications for Paleoceanography
• On Updating and Querying Submatrices
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method
• Incomplete Nested Dissection
• CADDeLaG: Framework for distributed anomaly detection in large dense graph sequences
• The Use of Presence Data in Modelling Demand for Transportation
• $\{-1,0,1\}$-APSP and (min,max)-Product Problems
• Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
• A rank 18 Waring decomposition of $s{M}_{⟨3⟩}$ with 432 symmetries
• The Descriptive Complexity of Subgraph Isomorphism without Numerics
• On Computing Min-Degree Elimination Orderings
• Roots multiplicity without companion matrices
• Efficiently Correcting Matrix Products
• Fast Computation on Semirings Isomorphic to $(\times ,\max )$ on ${\mathbb{R}}_{+}$
• Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
• Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication
• An Improved Combinatorial Algorithm for Boolean Matrix Multiplication
• Computing Valuations of the Dieudonné Determinants