Meta Flip Graph meets Serendipitous Product: new Fast Matrix Multiplication results
2026-06-01 • Symbolic Computation
Symbolic Computation
AI summaryⓘ
The authors improved ways to multiply small matrices faster by combining two advanced methods. They expanded their technique to cover 680 different small matrix sizes, and for many cases, they found better solutions than before. They also discovered new types of formulas that use simpler coefficients, which were not known previously. Their work includes 23 new special schemes for fast multiplication, adding to a group of known efficient methods. All their results and code are freely available.
matrix multiplicationmeta flip graph frameworkserendipitous productrectangular matrix formatstensor rankasymptotic exponentternary coefficientsinteger coefficientsrational coefficientsfast algorithm
Authors
A. I. Perminov
Abstract
This paper presents new results for fast matrix multiplication in small formats obtained by combining the meta flip graph framework with the serendipitous product construction. The framework has been extended to support all 680 rectangular formats with dimensions up to $16 \times 16 \times 16$. Compared to the previous state of the art, ranks are improved for 206 formats. For 84 formats, ternary schemes are found where previously only integer or rational coefficients were known. Additionally, 23 new schemes with asymptotic exponent $ω< \log_2 7$ are discovered, bringing the total number of such schemes to 52. The overall distribution of coefficient types across all investigated formats is 375 ternary, 18 integer, and 287 rational. All code and discovered schemes are available as open source.