Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
Open Access
- 12 July 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 227-236
Abstract
We give explicit low-rank bilinear non-commutative schemes for multiplying structured n × n matrices with 2 ≤ n ≤ 5, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over \(\mathbb {F}_2\) or \(\mathbb {F}_3\) and lifted to \(\mathbb {Z}\) or \(\mathbb {Q}\) . Using a flip graph search over tensor decompositions, we derive schemes for general, upper-triangular, lower-triangular, symmetric, and skew-symmetric inputs, as well as products of a structured matrix with its transpose. These schemes improve asymptotic constants for 13 of 15 structured formats. In particular, we obtain 4 × 4 rank-34 schemes for both multiplying a general matrix by its transpose and an upper-triangular matrix by a general matrix, improving the asymptotic factor from 26/41 (0.634) to 22/37 (0.595). Additionally, using \(\mathbb {F}_3\) flip graphs, we discover schemes over \(\mathbb {Q}\) that fundamentally require the inverse of 2, including a 2 × 2 symmetric-symmetric multiplication of rank 5 and a 3 × 3 skew-symmetric-general multiplication of rank 14 (improving upon AlphaTensor’s 15).
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- More Asymmetry Yields Faster Matrix Multiplication2025
- Finding Complex-Valued Solutions of Brent Equations Using Nonlinear Least SquaresComputational Mathematics and Mathematical Physics, 2024
- Discovering faster matrix multiplication algorithms with reinforcement learningNature, 2022
- Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans MethodFoundations of Computational Mathematics, 2016
- The bilinear complexity and practical algorithms for matrix multiplicationComputational Mathematics and Mathematical Physics, 2013
- Tensor rank is NP-completeJournal of Algorithms, 1990
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplicationComputers & Mathematics with Applications, 1982
- Partial and Total Matrix MultiplicationSIAM Journal on Computing, 1981
- Gaussian elimination is not optimalNumerische Mathematik, 1969