About
This is the accompanying website for our articles
- Marijn J.H. Heule, Manuel Kauers, and Martina Seidl, May 2019, New ways to multiply 3 x 3-matrices, Preprint
- Marijn J.H. Heule, Manuel Kauers, and Martina Seidl, July 2019, Local Search for Fast Matrix Multiplication, Proceedings of SAT'19. Preprint
- Marijn J.H. Heule, Manuel Kauers, and Martina Seidl, July 2019, A family of schemes for multiplying 3x3 matrices with 23 coefficient multiplications, Poster at ISSAC'19. Communications in Computer Algebra. Preprint
It contains the 3x3 matrix multiplication schemes we have discovered.
They are sorted by rank patterns.
Selecting a rank pattern in the upper selector loads the respective
scheme names into the lower selector.
Selecting a scheme name from the lower selector loads the scheme
into the large panel, where it can be inspected with various views.
For the sake of completeness, we have also included the previously
known schemes by Laderman, Smirnov, Courtois et al., and Oh et al.
All schemes in this collection are valid for any coefficient ring. The only numbers appearing as coefficients are +1, -1, and 0. Any two schemes are inequivalent, at least when the coefficient ring is the field with two elements.
Rank patterns
Each matrix multiplication scheme can be viewed as a \(23\times3\) table of \(3\times3\) matrices.
The rank pattern of a multiplication scheme is the \(23\times3\) table that contains the respective ranks.
The symmetry group of the matrix multiplication tensor permutes the rows and columns of the rank pattern,
so a suitably sorted table of the ranks can be used as an invariant of the group action.
On the left, we list our solutions separated according to this invariant.
The rank pattern names were chosen as follows.
Each column of a rank pattern is one of the 27 elements of \(\{1,2,3\}^3\).
To each of these tuples we associate a letter as indicated in the table below.
The rank pattern then corresponds to a string of 23 such letters.
As these strings tend to contain many repeated letters, we shorten them by a run length encoding.
For example, 10a2b2d2ef2jk3n represents the string aaaaaaaaaabbddeefjjknnn, which in turn
encodes the following rank pattern
| 11111111111111111222222 |
| 11111111111122222111222 |
| 11111111112211223112222 |
Here is the assignment between letters and columns:
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | A |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
As it may not be obvious by inspection whether two \(3\times23\) tables are equivalent modulo
permutation of rows and columns, we also provide two derived invariants that contain
less information but are more easy to compare. Writing the matrices in a scheme as
\((A_i,B_i,C_i)\) with \(i=1,\dots,23\), we define the polynomials
\[
f(x,y,z) = \sum_{\pi\in S_3}\pi\biggl(\sum_{i=1}^{23} x^{{\rm rk} A_i} y^{{\rm rk} B_i} z^{{\rm rk} C_i}\biggr),
\]
where the permutations \(\pi\) are meant to permute the variables \(x,y,z\), and
\[
g(w) = w^{\sum_{i=1}^{23}{\rm rk} A_i} + w^{\sum_{i=1}^{23}{\rm rk} B_i} + w^{\sum_{i=1}^{23}{\rm rk} C_i}.
\]
Families
In the following we list some families we extracted from our new schemes.
We include all families we found with 17 parameters.
Downloads