Consequences of the Moosbauer-Poole Algorithms
Manuel Kauers, and, Isaac Wood · 2025
Read Consequences of the Moosbauer-Poole Algorithms by Manuel Kauers, and, 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-2505-05896.txt.
Introduction
Manuel Kauers and Isaac Wood report, in a 2025 paper, new shortcuts for multiplying matrices. Two recent schemes by Moosbauer and Poole cut the multiplications needed for mid-size square matrices below long-standing counts. Kauers and Wood start from those schemes and search a graph of related variants, flipping between them to hunt for cheaper ones. Their search found improved schemes for various rectangular matrix shapes, not just squares.
Catalog record
| CREATOR | Manuel Kauers, and, Isaac Wood |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-05896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Consequences of the Moosbauer-Poole Algorithms
Manuel Kauers, and, Isaac Wood
Abstract
\vskip6.0pt Moosbauer and Poole have recently shown that the multiplication of two 5 × 5 5\times 5 matrices requires no more than 93 multiplications in the (possibly non-commutative) coefficient ring, and that the multiplication of two 6 × 6 6\times 6 matrices requires no more than 153 multiplications. Taking these multiplication schemes as starting points, we found improved matrix multiplication schemes for various rectangular matrix formats using a flip graph search.
More than half a century after the discovery of Strassen’s algorithm, we still
do not know how many multiplications in the ground ring are necessary for
multiplying an
n\times m
matrix with an
m\times p
matrix. The question is
not only open for asymptotically large matrices but for almost every specific
matrix format. The number of multiplications required by a particular matrix
multiplication scheme is called the
rank
of the scheme. For example,
the rank of the standard algorithm for multiplying
n\times m
matrices with
m\times p
matrices is
nmp
, and the rank of Strassen’s algorithm for multiplying
two
2\times 2
matrices is
7
, one less than the rank of the standard algorithm.
One of several known techniques to search for multiplication schemes of low rank
is the flip graph search
[
3
,
5
,
1
,
4
]
, which
takes a known matrix multiplication scheme for a certain format as input and
performs a sequence of operations on it with the goal of obtaining a variant
from which a multiplication can be eliminated. For several small matrix formats,
the multiplication schemes with the smallest rank known today were found with
this method. Most recently, Moosbauer and Poole
[
6
]
used a
variant of the flip graph method that takes symmetries into account in order to
obtain improvements for the formats
(n,m,p)=(5,5,5)
and
(n,m,p)=(6,6,6)
. Their schemes have rank 93 and 153, respectively.
For the present work, it is not necessary to know in detail how the flip graph
search works. It suffices to know that the search can start from an arbitrary
correct multiplication scheme for a certain format and then tries to eliminate
multiplications from it. A natural start point for the search is the standard
algorithm. While this choice works well for small matrix formats, it was already
observed by Kauers and Moosbauer
[
3
]
that it is not always the best choice. For
(5,5,5)
, they obtained a better result using a scheme found by
AlphaTensor
[
2
]
rather than the standard algorithm. Arai et al.
[
1
]
obtained
an even better result for
(5,5,5)
using an incremental approach. They
construct their starting points for a given format
(n,m,k)
from good schemes
they found for smaller formats. This works because matrices can be multiplied
blockwise. For example, a multiplication scheme of format
(3,3,4)
can be
obtained by patching together a scheme of format
(3,3,3)
and a scheme of
format
(3,3,1)
:
\begin{pmatrix}a_{1,1}&a_{1,2}&a_{1,3}\\
a_{2,1}&a_{2,2}&a_{2,3}\\
a_{3,1}&a_{3,2}&a_{3,3}\end{pmatrix}\cdot\begin{pmatrix}b_{1,1}&b_{1,2}&b_{1,3}&b_{1,4}\\
b_{2,1}&b_{2,2}&b_{2,3}&b_{2,4}\\
b_{3,1}&b_{3,2}&b_{3,3}\smash{\hbox to0.0pt{\kern 5.0pt\rule[-2.15277pt]{0.7pt}{35.00005pt}\hss}}&b_{3,4}\end{pmatrix}=\begin{pmatrix}c_{1,1}&c_{1,2}&c_{1,3}&c_{1,4}\\
c_{2,1}&c_{2,2}&c_{2,3}&c_{2,4}\\
c_{3,1}&c_{3,2}&c_{3,3}\smash{\hbox to0.0pt{\kern 5.0pt\rule[-2.15277pt]{0.7pt}{35.00005pt}\hss}}&c_{3,4}\end{pmatrix}.
Arai et al. obtained their improvement for
(5,5,5)
by a sequence of flip graph searches for the formats
(2,2,2)
,
(2,2,3)
,
(2,3,3)
,
(3,3,3)
,
(3,3,4)
,
(3,4,4)
,
(4,4,4)
,
(4,4,5)
,
(4,5,5)
,
(5,5,5)
, always taking starting points obtained by extending the results of the search of the
previous format (cf. Fig.
1
, left).
222
223
233
333
334
344
444
445
455
555
455
456
457
466
467
477
555
556
557
566
567
577
666
667
677
Figure 1:
Left: Arai et al. obtained a good scheme for
(5,5,5)
starting from a scheme of size
(2,2,2)
by following the
depicted path.
Right: We performed flip graph searches for various formats, using starting points obtained along the indicated
arrows from the schemes found by Moosbauer and Poole for
(5,5,5)
and
(6,6,6)
. For some formats, we tried
several paths.
In the same spirit, we explore formats in the vicinity of
(5,5,5)
, taking the Moosbauer-Poole algorithms as
basis. In addition to extending known schemes to schemes of larger format, we can also use a known
scheme to construct promising starting points for smaller formats, by simply setting some variables
to zero. For example, every scheme of format
(3,3,3)
contains a scheme of format
(2,3,3)
via
\begin{pmatrix}a_{1,1}&a_{1,2}&a_{1,3}\\
a_{2,1}&a_{2,2}&a_{2,3}\\
0&0&0\end{pmatrix}\cdot\begin{pmatrix}b_{1,1}&b_{1,2}&b_{1,3}\\
b_{2,1}&b_{2,2}&b_{2,3}\\
b_{3,1}&b_{3,2}&b_{3,3}\end{pmatrix}=\begin{pmatrix}c_{1,1}&c_{1,2}&c_{1,3}\\
c_{2,1}&c_{2,2}&c_{2,3}\\
0&0&0\end{pmatrix}.
Altogether, we considered the formats shown in Fig.
1
on the right. The arrows indicate from
where the starting points of the flip graph search were obtained.
Because of the symmetry of the matrix multiplication tensor, it suffices to consider
formats
(n,m,k)
with
n\leq m\leq k
.
As an example, consider the format
(5,6,7)
. As illustrated in Fig.
1
, we
approached this format from
(5,6,6)
and from
(5,5,7)
. For the format
(5,6,6)
we have a multiplication scheme of rank 130. Extending this scheme to
a scheme for
(5,6,7)
costs
5\times 6=30
additional multiplications. So the
starting point in this case is a scheme of rank 160. A flip graph search brings
this down to 150. For
(5,5,7)
we have a scheme of rank 127, which extends to
a scheme for
(5,6,7)
of rank 162. In this case, the flip graph search could
bring only down to 152, so the first attack yielded the better result.
Some arrows are computationally more expensive than others, for reasons that are
unclear. On the average, we have spent roughly one day of computation time on a
machine with 100 cores for each arrow.
The results of all our computations are summarized in the table below. It turns
out that there are improvements for all formats except for
(4,6,6)
and
(6,7,7)
, and in some cases the improvement is considerable. The column
“previous record” refers to the best known rank according to Sedoglavic’s
table
[
7
]
as of April 2025. These ranks refer to ground fields of
characteristic zero.
Our flip graph search first produces schemes for the ground field
\mathbb{Z}_{2}
.
In order to translate them to schemes with integer coefficients, we attempted to
apply Hensel lifting, and most cases, at least one of the schemes with the
smallest rank over
\mathbb{Z}_{2}
could be lifted to a scheme with integer
coefficients. For
(4,5,5)
, we only found schemes of rank 74 over
\mathbb{Z}_{2}
which cannot be lifted, like Arai et al.
[
1
]
. Also none of the schemes
of rank 75 we found for this format can be lifted, but some of rank 76 can. For
(6,7,7)
, the schemes we found of rank 221 can also not be lifted, but in this
case we did not spend a lot of effort finding schemes with integer coefficients
because 221 is larger than the best known rank.
format
naive
previous
our
rank
record
rank
(4,5,5)
100
76
76
(4,5,6)
120
93
90
(4,5,7)
140
109
104
(4,6,6)
144
105
106
(5,5,6)
150
116
110
(4,6,7)
168
125
123
(5,5,7)
175
133
127
(5,6,6)
180
137
130
(4,7,7)
196
147
144
(5,6,7)
210
159
150
(5,7,7)
245
185
176
(6,6,7)
252
185
183
(6,7,7)
294
215
221
(over
\mathbb{Z}_{2}
)
The multiplication schemes announced here are publicly available at
https://github.com/mkauers/matrix-multiplication