Exploring Commutative Matrix Multiplication Schemes via Flip Graphs

Isaac Wood · 2025

Read Exploring Commutative Matrix Multiplication Schemes via Flip Graphs by Isaac Wood (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-2506-22113.txt.

Introduction

Isaac Wood explores faster matrix multiplication in the commutative setting in a 2025 paper. Flip graphs, a search method over multiplication schemes, had worked well for the standard non commutative problem but stumbled when products were forced to commute. Two fixes are proposed, plus a hybrid of them.

One route builds a commutative tensor modeled on a known three by three method and approximates its rank with the classic flip graph. The second defines a fully commutative flip graph on a quotient tensor space. Across sizes up to five by five the methods recover the best known multiplication counts, though no new record fell. Larger sizes look promising.

Catalog record

CREATORIsaac Wood
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-22113

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exploring Commutative Matrix Multiplication Schemes via Flip Graphs Thanks: Supported by the Austrian FWF grant 10.55776/PAT8258123 Isaac Wood Abstract . We explore new approaches for finding matrix multiplication algorithms in the commutative setting by adapting the flip graph technique: a method previously shown to be effective for discovering fast algorithms in the non-commutative case. While an earlier attempt to apply flip graphs to commutative algorithms saw limited success, we overcome both theoretical and practical obstacles using two strategies: one inspired by Marakov’s algorithm to multiply 3x3 matrices, in which we construct a commutative tensor and approximate its rank using the standard flip graph; and a second that introduces a fully commutative variant of the flip graph defined via a quotient tensor space. We also present a hybrid method that combines the strengths of both. Across all matrix sizes up to 5x5, these methods recover the best known bounds on the number of multiplications and allow for a comparison of their efficiency and efficacy. Although no new improvements are found, our results demonstrate strong potential for these techniques at larger scales. 1. Introduction The computational cost of matrix multiplication is a famous open problem in algebraic complexity theory. In 1969, Strassen [ 14 ] discovered that the n^{3} multiplications needed to multiply matrices isn’t optimal, and found an algorithm to multiply 2\times 2 matrices in only 7 multiplications, leading to an algorithm for multiplying n\times n matrices in O(n^{2.805\dots}) ground field operations. This led to extensive research in similar algorithms, with the most recent optimization finding multiplication being done in O(n^{2.37133\dots}) by Alman et al. [ 1 ] . All these discoveries rely on the algorithms that do not assume commutativity of multiplication, which is crucial for using the algorithm recursively; for instance, Strassen’s algorithm computes the product of 2^{k}\times 2^{k} matrices in 7^{k} field multiplications. However, leveraging commutativity can yield algorithms that use fewer multiplications. Notably, Winograd [ 16 ] found an algorithm using around n^{3}/2 multiplications that exploited commutativity in 1967, two years earlier than Strassen’s algorithm. This commutative algorithm was improved upon by Waksman in 1970 [ 15 ] , and this remains one of the fastest practical ways to multiply small matrices [ 17 ] . Since then, there has been substantial progress in commutative algorithms, we particularly note Marakov’s [ 8 ] algorithm for multiplying 3\times 3 matrices in only 22 multiplications, one fewer than Laderman’s [ 7 ] algorithm without commutativity which uses 23 multiplications. Rosowski [ 12 ] showed that to multiply an l\times m matrix by a m\times n matrix, you need only (m(ln+l+n-1)+n-1)/2 multiplications if m is odd and n is even, and otherwise you need only m(ln+l+n-1)/2 multiplications. For non-commutative algorithms, there have been advancements in searches for the fewest multiplications for specific small sizes. Smirnov [ 13 ] used a numerical approach to find improvements in several sizes, Kauers et al. [ 4 ] used SAT-solvers to find many 3\times 3 multiplication schemes matching Laderman’s 23 multiplications, and very recently Google’s AlphaEvolve [ 11 ] found improvements in several sizes as well using its own method, including a 4\times 4 scheme with 48 multiplications using non-real coefficients: a result now matched over rings with 1/2 by Dumas et al. [ 3 ] . The recent method we will be focusing on is the flip graph. This approach involves traversing a connected graph of all Strassen-like algorithms, in the hope of finding one that needs very few multiplications. This approach has yielded significant advancements, as demonstrated in works by Kauers, Moosbauer, Poole, Wood, Arai, Ichikawa and Hukushima [ 5 , 2 , 10 , 6 ] . To our knowledge, no computer searches have been successfully applied to find commutative schemes. Our work here uses flip graphs to find commutative algorithms. Previous attempts to apply flip graphs to the commutative setting by Moosbauer [ 9 ] have been unsuccessful. He suggests there may have been a bug in his implementation, not allowing for rectangular matrix multiplications to work properly. We also tackle this differently from Moosbauer, using three approaches. One in which we can use the commutativity of the multiplications within a generalized flip graph, one in which we use the commutativity before applying a flip graph search in a clever way inspired by Marakov’s 3\times 3 algorithm and then we attempt to combine these approaches to find a fast and accurate method. We compare the three methods by using them to find bounds on the number of multiplications needed for all matrix sizes up to multiplying two 5\times 5 matrices. In these sizes, the best known bound is given by a slight improvement to Rosowski’s bound we found, noting that AB=(B^{T}A^{T})^{T} . We find that using the standard flip graph search on a modified tensor is about 30 times faster than using the commutative tensor, though this comes at the cost of not matching Rosowski’s bound in all matrix sizes, while the commutative flip graph was able to match this bound in every case. The combined approach achieved a favourable balance between efficacy and speed, matching Rosowski’s bound in almost all matrix sizes and being around three times faster than the full commutative flip graph approach. Overall, these computational methods were able to match Rosowski’s rank in every size of matrix multiplication we looked at and showed great promise for finding improvements on these ranks for bigger sizes, though unfortunately we did not find improvements for any sizes we looked at. 2. Background Let \mathbb{F} be a field, R be an \mathbb{F} -algebra and \mathbf{A}\in R^{l\times m},\mathbf{B}\in R^{m\times n} . Recall that a Strassen-like algorithm for computing \mathbf{AB} works in two steps: first we perform r multiplications in R , then we take some linear combinations of these products to obtain the entries of \mathbf{AB} . For example, in Strassen’s algorithm, we have l=m=n=2 : let \mathbf{A}=\begin{pmatrix}A_{11}&A_{12}\\ A_{21}&A_{22}\end{pmatrix},\mathbf{B}=\begin{pmatrix}B_{11}&B_{12}\\ B_{21}&B_{22}\end{pmatrix},\mathbf{AB}=\begin{pmatrix}C_{11}&C_{12}\\ C_{21}&C_{22}\end{pmatrix} so we get \displaystyle m_{1} \displaystyle=(A_{11}+A_{22})(B_{11}+B_{22}) \displaystyle m_{2} \displaystyle=(A_{21}+A_{22})B_{11} \displaystyle m_{3} \displaystyle=A_{11}(B_{12}-B_{22}) \displaystyle m_{4} \displaystyle=(A_{12}+A_{11})B_{22} \displaystyle m_{5} \displaystyle=A_{22}(B_{21}-B_{11}) \displaystyle m_{6} \displaystyle=(A_{21}-A_{11})(B_{11}+B_{12}) \displaystyle m_{7} \displaystyle=(A_{12}-A_{22})(B_{22}+B_{21}) \displaystyle C_{11} \displaystyle=m_{1}-m_{4}+m_{5}+m_{7} \displaystyle C_{12} \displaystyle=m_{3}+m_{4} \displaystyle C_{21} \displaystyle=m_{2}+m_{5} \displaystyle C_{22} \displaystyle=m_{1}-m_{2}+m_{3}+m_{6}. This allows us to compute \mathbf{AB} using only 7 multiplications. We often represent these algorithms using the language of tensors, which is formalized as follows: Definition 2.1 . Let l,m,n\in\mathbb{N} . Let V_{1,l,m}=\mathbb{F}^{l\times m},V_{2,m,n}=\mathbb{F}^{m\times n},V_{3,n,l}=\mathbb{F}^{n\times l} be vector spaces over \mathbb{F} . Let \{a_{ij}:1\leq i\leq l,1\leq j\leq m\} be a basis for V_{1,l,m} , \{b_{ij}:1\leq i\leq m,1\leq j\leq n\} be a basis for V_{2,m,n} and \{c_{ij}:1\leq i\leq n,1\leq j\leq l\} be a basis for V_{3,n,l} . Define the matrix multiplication tensor \mathcal{M}_{l,m,n}\in V_{1,l,m}\otimes V_{2,m,n}\otimes V_{3,n,l} to be \mathcal{M}_{l,m,n}=\sum_{i,j,k=1}^{l,m,n}a_{ij}\otimes b_{jk}\otimes c_{ki}. Remark 2.2 . This tensor in fact does encode matrix multiplication. Let A,B,C be matrix spaces over \mathbb{F} with dimension l\times m , m\times n and l\times n . We can now define an isomorphism \Phi:V_{1,l,m}\otimes V_{2,m,n}\otimes V_{3,n,l}\rightarrow\text{Bil}(A,B;C) defined by \Phi(a_{i_{1}j_{1}}\otimes b_{j_{2}k_{1}}\otimes c_{k_{2}i_{2}})=\phi_{i_{1},i_{2},j_{1},j_{2},k_{1},k_{2}} where \phi_{i_{1},i_{2},j_{1},j_{2},k_{1},k_{2}}(\alpha,\beta)=\alpha_{i_{1}j_{1}}\beta_{j_{2}k_{1}}\Gamma_{i_{2}k_{2}} where \alpha\in A,\beta\in B,\Gamma_{i_{2}k_{2}}\in C ; \alpha_{ij},\beta_{ij} represent the elements in \alpha or \beta respectively in the (i,j) -th entry; \Gamma_{ij} is the matrix with all zeroes except a one at the (i,j) -th entry. Note that the c_{ij} correspond to \Gamma_{ji} ; this is standard to keep the

Read the complete text