Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
Kirill Khoruzhii 1,∗ , Patrick Gelß 1 , Sebastian Pokutta 1,2 · 2025
Read Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search by Kirill Khoruzhii 1,∗ , Patrick Gelß 1 , Sebastian Pokutta 1,2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10786.txt.
Introduction
Kirill Khoruzhii, Patrick Gelß, and Sebastian Pokutta find faster ways to multiply structured matrices, the kind with symmetry or triangular patterns that appear throughout scientific computing. Their schemes are explicit low-rank bilinear algorithms for small matrices, which serve as building blocks that recursive methods amplify into better long-run scaling.
A flip graph search over tensor decompositions discovers the schemes over small finite fields, which are then lifted to the integers and rationals. The haul covers general, triangular, symmetric, and skew-symmetric inputs, plus products of a matrix with its transpose, improving the constants for thirteen of fifteen structured formats. One new scheme even beats a result from DeepMind's AlphaTensor, multiplying a small skew-symmetric matrix by a general one with one fewer multiplication.
Catalog record
| CREATOR | Kirill Khoruzhii 1,∗ , Patrick Gelß 1 , Sebastian Pokutta 1,2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-10786
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search Kirill Khoruzhii 1,∗ , Patrick Gelß 1 , Sebastian Pokutta 1,2 Abstract We give explicit low-rank bilinear non-commutative schemes for multiplying structured n × n n\times n matrices with 2 ⩽ n ⩽ 5 2\leqslant n\leqslant 5 , which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over 𝔽 2 \mathbb{F}_{2} or 𝔽 3 \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 4\times 4 rank- 34 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 8 / 13 8/13 (0.615) to 22 / 37 22/37 (0.595). Additionally, using 𝔽 3 \mathbb{F}_{3} flip graphs, we discover schemes over ℚ \mathbb{Q} that fundamentally require the inverse of 2 2 , including a 2 × 2 2\times 2 symmetric-symmetric multiplication of rank 5 5 and a 3 × 3 3\times 3 skew-symmetric-general multiplication of rank 14 14 (improving upon AlphaTensor’s 15 15 ). Figure 1: Strassen’s decomposition rank- 7 for 2\times 2 matrix multiplication. a) Matrix product written as a bilinear contraction. b) The seven intermediate products. c) Output reconstructed entries. d) Tensor view: T_{ijk} expressed as a sum of seven rank-1 terms; each term corresponds to one intermediate product m_{\ell} in (b) and encodes how it contributes to each output c_{k} in (c). 1 1 footnotetext: [email protected] 1. Introduction Modern computational workflows rely heavily on matrix multiplication, in particular for matrices with exploitable structure. Expressions such as XX^{\textnormal{T}} appear throughout statistics as covariance or Gram matrices, in optimization algorithms for computing Newton-Schulz updates in modern LLM training methods 19 ; 24 ; 11 , and in linear regression where solutions involve the data covariance matrix. Similarly, triangular matrix multiplication arises naturally when working with factorizations or solving triangular systems, and also in the masking used for causal attention in transformer-based neural networks 20 . Unlike general matrix multiplication, these structured products offer opportunities for constant-factor improvements even when asymptotic complexity matches the general case. These operations correspond to Level 3 BLAS primitives: SYRK (symmetric rank-k update) computes AA^{\textnormal{T}} , TRMM (triangular matrix multiply) handles products involving triangular matrices, and related operations form the computational backbone of numerical linear algebra libraries. Despite their prevalence in applications, structured matrix-matrix products have received far less systematic attention 19 than general multiplication in the algorithmic discovery literature. Since Strassen showed the naive O(n^{3}) algorithm is suboptimal 23 , research has followed two main directions. One branch pursues improvements to the asymptotic exponent \omega , where recent laser-method refinements 1 have pushed the bound to \omega<2.372 . The other branch focuses on practical algorithms 18 ; 21 for fixed small matrix sizes as base, seeking low-rank bilinear decompositions that minimize the number of scalar multiplications for specific formats. Computing or even approximating the minimal tensor rank is NP-hard 9 . Constant-factor improvements translate to performance gains in practice, particularly for recursive algorithms where small-base schemes serve as building blocks. For structured products, the asymptotic complexity remains \Theta(n^{\omega}) as it does for general multiplication, but the multiplicative constants can differ, creating opportunities for specialized algorithms that exploit structure. Automated methods now efficiently find low-rank tensor decompositions. Numerical optimization 22 ; 12 , and deep reinforcement learning approaches such as AlphaTensor 8 have successfully discovered state-of-the-art schemes for general matrix multiplication, though often requiring substantial computational resources. Random walks in flip graphs 13 enable discovery of competitive schemes on standard hardware by restricting search to correct decompositions. However, systematic application of these automated methods has focused almost exclusively on general matrix multiplication 2 ; 16 ; 15 ; 14 ; 10 and polynomial multiplication 3 . For structured products, prior work consists of representation-theoretic matrix-vector constructions 26 ; 27 and scattered results for specific formats 5 ; 8 ; 19 , but no comprehensive framework exists for discovering and cataloging schemes across the full range of structured matrix-matrix operations. We systematically explore structured matrix multiplication via flip graph search and catalog schemes for all 15 distinct format combinations (after accounting for symmetries) with base sizes n\in\{2,3,4,5\} . We extend this methodology in two key directions. First, we perform searches over \mathbb{F}_{3} in addition to \mathbb{F}_{2} , enabling discovery of schemes that fundamentally require the inverse of 2 and successfully lift them to \mathbb{Q} . Second, we introduce specialized techniques for structured tensors that, in transpose-product formats, increase the fraction of recursive calls. Our approach achieves systematic exploration of the structured multiplication landscape on standard hardware, improving asymptotic complexity factors for 13 of 15 structured formats considered. Notable improvements include computing AA^{T} and triangular-general multiplication, both corresponding to fundamental Level 3 BLAS primitives. We also discover schemes over \mathbb{F}_{3} requiring the inverse of 2, including a 2\times 2 symmetric-symmetric multiplication of rank 5 and a 3\times 3 skew-symmetric-general multiplication of rank 14, improving on ranks 6 and 15, respectively 27 ; 8 . The remainder of this paper is organized as follows. Section 2 reviews matrix multiplication as tensor decomposition and introduces our notation for structured formats. Section 3 defines structured matrix multiplication formally, establishes the notation \langle n_{1},n_{2},n_{3}:r\rangle_{\mathtt{ab}}^{(q_{\mathtt{ab}},q_{\mathtt{ag}},q_{\mathtt{gb}})} for recursive schemes, and derives the general asymptotic complexity formula. Section 4 describes the flip graph construction, proves its connectivity properties, and explains the operations (flips, reductions, plus-transitions) that generate edges. Section 5 details our methodology for identifying recursive schemes through Hensel lifting from \mathbb{F}_{2} or \mathbb{F}_{3} to \mathbb{Z} or \mathbb{Q} , including our corner-zeroing technique for transpose products. Section 6 presents our complete results with comparisons to prior work. Section 7 discusses extensions to other bilinear computations, multi-objective optimization challenges, and prospects for directed search on flip graphs. Figure 2: Decomposition rank- 17 for 3\times 3 matrix multiplication GG^{\textnormal{T}} . a) Block layout C=GG^{\textnormal{T}} with G partitioned into 3\times 3 blocks A_{1},\ldots,A_{9} ; by symmetry only six distinct blocks C_{1},\ldots,C_{6} should be calculated. b) General products m_{1},\ldots,m_{8} . c) Nine recursive calls r_{1},\ldots,r_{9} computing the symmetric block products A_{i}A_{i}^{\textnormal{T}} . d) Reconstruction of C_{1},\ldots,C_{6} from the m ’s and r ’s. e) Tensor view: contraction tensor T_{ijk} expressed as a sum of rank-1 terms. 2. Algorithms as Tensor Decomposition Matrix multiplication (Fig. 1 a) can be written as a bilinear mapping (\boldsymbol{a},\boldsymbol{b})\mapsto\boldsymbol{c} with c_{k}=\sum_{i,j}T_{ijk}\,a_{i}b_{j} . A canonical polyadic decomposition (CPD) of the tensor T_{ijk}=\sum_{q=1}^{r}U_{qi}V_{qj}W_{qk} (1) provides a recipe to compute \boldsymbol{c} using r multiplications: c_{k}=\sum_{q=1}^{r}W_{qk}\big(\textstyle{\sum_{i}}U_{qi}a_{i}\big)\big(\textstyle{\sum_{j}}V_{qj}b_{j}\big). (2) Here a_{i} and b_{j} denote entries of the vectorized input matrices. We regard multiplications by U and V (linear combinations of inputs) as inexpensive compared to the r scalar multiplications between the two parenthesized terms. Algorithmic complexity equals r , the number of scalar multiplications. The coefficients U_{qi} , V_{qj} , W_{qk} in ( 1 ) can be integers, rationals, or elements of finite fields. We discover schemes over the finite fields \mathbb{F}_{2} and \mathbb{F}_{3} , then apply Hensel