PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Matrix Multiplication in Small Formats: Discovering New Schemes with an Open-Source Flip Graph Framework

A. I. Perminov

arXiv:2603.02398v1cs.SC

TL;DR

Matrix multiplication scheme discovery needs methods that improve rank while producing coefficients practical for implementation. This paper presents an open-source, multi-ring flip graph framework for large-scale searches and reports 79 rank improvements, including a 115-multiplication 4 × 4 × 10 scheme. The released tools and schemes support reproducible exploration, while the results remain bounded by differences between coefficient rings and variation in search difficulty.

  • Problem

    Small matrix formats require low-rank schemes, while coefficients such as large integers or fractions can impose hardware overhead compared with ZT additions and subtractions.

  • Method

    An open-source C++ flip graph framework searches across Z2, Z3, and ZT using fixed-dimension and meta-dimensional operators, bit-level encoding, and OpenMP parallelism.

  • Results

    79 matrix multiplication schemes improved rank, including a 4 × 4 × 10 scheme requiring 115 multiplications and achieving ω ≈2.80478 for this specific size.

  • Takeaways & Limitations

    93 schemes previously known only over rationals or integers were rediscovered in ZT coefficients and are directly suitable for implementation without multiplication by constants.

  • Takeaways & Limitations

    Search behavior varies across schemes and restricted coefficient rings can fail to reach ranks known for rational schemes, as illustrated by 3 × 3 × 6 alternatives not converted to integers.

Abstract

from arXiv · show

An open-source C++ framework for discovering fast matrix multiplication schemes using the flip graph approach is presented. The framework supports multiple coefficient rings -- binary ($\mathbb{Z}_2$), modular ternary ($\mathbb{Z}_3$) and integer ternary ($\mathbb{Z}_T = \{-1,0,1\}$) -- and implements both fixed-dimension and meta-dimensional search operators. Using efficient bit-level encoding of coefficient vectors and OpenMP parallelism, the tools enable large-scale exploration on commodity hardware. The study covers 680 schemes ranging from $(2 \times 2 \times 2)$ to $(16 \times 16 \times 16)$, with 276 schemes now in $\mathbb{Z}_T$ coefficients and 117 in integer coefficients. With this framework, the multiplicative complexity (rank) is improved for 79 matrix multiplication schemes. Notably, a new $4 \times 4 \times 10$ scheme requiring only 115 multiplications is discovered, achieving $ω\approx 2.80478$ and beating Strassen's exponent for this specific size. Additionally, 93 schemes are rediscovered in ternary coefficients that were previously known only over rationals or integers, and 68 schemes in integer coefficients that previously required fractions. All tools and discovered schemes are made publicly available to enable reproducible research.

1 Introduction

The paper presents an open-source flip graph framework for discovering fast matrix multiplication schemes with practical coefficient rings. It reports rank improvements and rediscoveries of schemes using ternary and integer coefficients.

  • The study targets small formats where rank minimization matters and ZT coefficients enable implementation through additions and subtractions.Large integers or fractions can incur hardware overhead.
  • The framework implements the flip graph approach across Z2, Z3, and ZT coefficient rings using efficient bit-level encoding.
  • 79 matrix multiplication schemes have improved rank, including a 4 × 4 × 10 scheme using 115 multiplications and achieving ω ≈2.80478.The reported exponent is better than Strassen’s for this specific size.
  • 93 schemes previously known only over rationals or integers were rediscovered with ternary integer coefficients (ZT).
  • 68 schemes previously requiring fractions were rediscovered with integer coefficients.
  • The source code and discovered schemes are released openly to support reproducible research and community-driven exploration.

2 Related Work

Related work spans automated search methods including SAT, numerical optimization, constraint programming, reinforcement learning, and flip graph exploration. The paper builds on flip graph advances while emphasizing practical coefficient rings and open implementation.

  • SAT solving can find (2, 2, 2 : 7) schemes in seconds but exhaustive solving for (3, 3, 3 : 23) can run for days without finding solutions.
  • Hybrid SAT and local-search methods have discovered more than 17000 non-equivalent (3, 3, 3 : 23) schemes despite pure SAT scalability limits.
  • Numerical optimization can produce approximate solutions that round to exact coefficients, but the resulting fractions or large integers are not always easy to convert into practical rings.
  • The flip graph approach represents valid schemes as vertices and correctness-preserving local transformations as edges, enabling systematic algorithm-space exploration.
  • Meta flip graphs extend the search across matrix dimensions, expanding the space reachable by flip-based methods.
  • The present framework builds on meta flip graphs with an open-source implementation focused on ZT coefficients, bit-level performance, and uniform support for multiple rings.

3 Preliminaries

Matrix multiplication schemes encode computations through three coefficient tensors whose rank-one components produce intermediate products and recombine them into the result. The flip graph then searches valid schemes through correctness-preserving local and global transformations, including operators that change dimensions and coefficient-ring representations.

  • Matrix Multiplication Schemes: A rank-r scheme uses coefficient tensors U, V, and W to compute r intermediate products and recombine them into C = AB.The tensors organize linear combinations of entries from A and B, followed by recombination coefficients from W.
  • Matrix Multiplication Schemes: Comparing coefficients in C = AB yields polynomial constraints known as Brent equations, with Kronecker deltas enforcing the required products.The formulation uses C^T for more symmetric Brent equations during search.
  • Core Operators: The flip graph represents valid schemes as vertices connected by local transformations that preserve correctness.Operators can be applied to permutations of the U, V, and W tensors.
  • Core Operators: Flip and reduction decrease rank by eliminating redundant components, whereas plus and split increase rank while preserving correctness.Expand combines plus and split by selecting one of the two transformations uniformly at random.
  • Core Operators: Sandwiching applies invertible matrices to all rank-one components, preserving correctness and rank while restructuring coefficient distributions.Scalar matrices provide the special case of rescaling the triple factors.
  • Meta Flip Graph Operators: Merge, product, extend, and project navigate between matrix dimensions by combining, multiplying, enlarging, or reducing schemes.These meta-dimensional operators are valid under arbitrary dimension permutations and expand the reachable search space.
  • Coefficient Rings: The framework distinguishes binary Z2, modular ternary Z3, integer ternary ZT, integer Z, and rational Q coefficient rings.ZT is separated from Z because coefficients outside {-1,0,1} are less efficient for hardware implementation.
  • Coefficient Rings: The practical distinction between ZT and Z is hardware efficiency: Z schemes contain at least one coefficient with absolute value greater than 1.ZT is technically a subset of Z, but the paper labels it separately for practical purposes.

4 The Flip Graph Framework: Design and Implementation

The framework is an open-source C++ implementation of flip-graph search for fast matrix multiplication schemes. It combines multiple coefficient-ring representations, bit-level operations, parallel random walks, and lifting procedures to support reproducible exploration on commodity hardware.

  • Design principles: The framework supports Z2, Z3, and ZT coefficient rings, with ZT schemes immediately valid over arbitrary rings without lifting.
  • Coefficient encoding: Bit-level encoding packs coefficient vectors into unsigned integers, reducing operations over up to 128 elements to a small number of bitwise operations.Supported integer types range from uint16_t to __uint128_t, limiting each matrix to at most 128 elements per coefficient vector.
  • Search tools: The framework provides fixed-dimension flip_graph and meta-dimensional meta_flip_graph tools, alongside tools for alternative-scheme generation, lifting, and metric optimization.meta_flip_graph supports project, extend, merge, and product operations that can change scheme dimensions.
  • Random-walk search: Parallel random walks assign independent runners to different search regions, using flips, rank-increasing expands, and probabilistic reductions or sandwiching operations.Flips preserve rank, while expand operations help escape local optima and reductions can decrease rank.
  • Random-walk search: A configurable reset mechanism returns stalled runners to recent improvements, discarding unproductive paths while restarting from promising regions.The recent-improvement pool is a circular buffer typically sized at 10, with initial schemes included when necessary.
  • Lifting: Hensel lifting solves linear systems involving the Jacobian of the Brent equations and the matrix multiplication tensor, followed by rational reconstruction.The underdetermined systems admit multiple solutions whose choices affect whether reconstruction yields compact ternary or integer coefficients, or large fractions.

5 Constructing New Schemes from Existing Ones

The framework constructs larger matrix multiplication schemes by composing existing schemes algebraically or placing them within block matrix multiplication. These constructions provide valid starting points for flip-graph optimization and upper bounds beyond the encoding limit.

  • Algebraic composition: Merge, extend, and product combine existing schemes into larger dimensions, with merge summing ranks and product multiplying ranks.Extend increases dimensions incrementally, and these operations are associative and repeatable.
  • Block matrix multiplication: For sufficiently large dimensions, merge and product can yield ranks far from optimal, motivating block matrix multiplication with a carefully chosen base scheme.
  • Block matrix multiplication: A base scheme determines how partitioned blocks of A, B, and C are combined in each block multiplication.The numbers of blocks define the dimensions of the base scheme, while target dimensions determine the actual block sizes.
  • Block matrix multiplication: In the (4, 7, 15) example, Strassen’s 2 × 2 × 2 base scheme yields a total rank of 307 multiplications across seven block multiplications.The rank is computed as 51+35+45+40+51+45+40 = 307.
  • Construction scope: These constructions supply valid schemes for flip-graph searches within the 128-element limit, while larger schemes are reported directly as discovered upper bounds.

6 Results

Extensive searches covered matrix multiplication formats through 16 × 16 × 16 and improved ranks, coefficient practicality, and known upper bounds. The headline result is a new 4 × 4 × 10 scheme using 115 multiplications with exponent ω ≈2.80478.

  • Improved ranks: 79 matrix multiplication schemes received improved ranks through the framework’s searches across dimensions up to 16 × 16 × 16.The experiments used a 12-core laptop, a 20-core workstation, and a 96-core institutional cluster, executing billions of iterations.
  • Improved ranks: 115 multiplications give the new 4×4×10 scheme an exponent ω ≈2.80478, strictly better than Strassen’s exponent for this specific size.The paper cautions that fixed-format asymptotic exponents are not directly comparable, but this scheme is more efficient than recursively applying Strassen’s algorithm to that size.
  • Coefficient rings: 93 formats gained alternative schemes with the same best-known rank using coefficients in {−1, 0, 1}, replacing previously rational or integer-only representations.Ternary coefficients make the schemes directly suitable for implementation with additions and subtractions.
  • Coefficient rings: 68 schemes that previously required fractions were rediscovered using integer coefficients only.The paper describes integer coefficients as less efficient than ternary coefficients but preferable to fractions for practical implementation.
  • Scheme distribution: The tracked collection contains 680 schemes: 276 ternary, 117 integer, and 287 rational.These correspond to 40.6%, 17.2%, and 42.2%, respectively.
  • Scheme distribution: 29 tracked schemes have rank lower than Strassen’s algorithm would achieve at their specific dimensions, including the newly discovered 4 × 4 × 10 scheme.The remaining 28 such schemes were previously known.

7 Discussion

The discussion identifies strong variability in flip-graph behavior and exponent trends across formats, while highlighting unresolved gaps between coefficient rings and limits of current search heuristics. It also points to computational scaling and broader evaluation as key directions for future work.

  • Search Variability: Search behavior varied substantially: 4 × 4 × 4 often improved quickly, whereas 2 × 4 × 5 and 3 × 3 × 6 required more iterations.
  • Limitations and Future Directions: Current limitations include non-transferable format-specific behavior, imperfect constrained lifting, and progress limited by available computational resources.The discussion calls for broad evaluation, improved lifting methods, and larger-scale distributed searches.
  • Exponent Trends: 4 × 4 × 9 and 4 × 4 × 10 fell below Strassen’s exponent, then rose again for larger p.Exponent trends also differed by format: 6 × 9 × p generally decreased while 5 × 5 × p generally increased.
  • Exponent Trends: Downward spikes at p = 12 suggest efficient m × n × 12 constructions, possibly influenced by block propagation from 3 × 3 × 6 and 3 × 4 × 6 schemes.The full explanation remains an open question.
  • The Gap Between Coefficient Rings: Rank-40 integer or ternary schemes remain elusive for 3 × 3 × 6, while restricted-ring searches reach rank 33 versus rational rank 32 for 2 × 4 × 5.The authors frame the existence of same-rank integer or ternary schemes as an unresolved question.

8 Conclusion

The paper presents an open-source C++ flip-graph framework supporting multiple coefficient rings and large-scale search on commodity hardware. It reports 79 rank improvements, including a 115-multiplication 4 × 4 × 10 scheme, alongside ternary and integer rediscoveries, and releases the tools and schemes for reproducible community research.

  • 79 matrix multiplication schemes received rank improvements across various dimensions.
  • 115 multiplications suffice for a new 4 × 4 × 10 scheme with ω ≈2.80478, more efficient than recursively applying Strassen’s algorithm for that size.
  • 93 schemes previously known only over rationals or integers were rediscovered with ternary integer coefficients, avoiding multiplication by constants.
  • 68 schemes previously requiring fractions were rediscovered using integer coefficients only.
  • Flip potential correlates with the likelihood of further improvement and may help identify promising candidates for future searches.The paper explicitly treats this as a heuristic, not a rigorous guarantee.
  • Future work targets distributed scaling, systematic flip-potential evaluation, coefficient-ring relationships, and improved lifting for more compact coefficients.
  • The open-source framework and discovered schemes are released to support reproducible, community-driven discovery.

A Schemes with Exponent Below Strassen’s Bound

Table 4 catalogs matrix multiplication formats up to 16 × 16 × 16 whose exponent is strictly below Strassen’s bound. It reports each format’s rank, coefficient ring, and resulting exponent, including a newly discovered 4 × 4 × 10 scheme.

  • 115 multiplications yield the newly discovered 4 × 4 × 10 scheme.The remaining 28 listed schemes were previously known and included for completeness.
  • Each listed format has dimensions no larger than 16 × 16 × 16 and exponent strictly below Strassen’s bound.The table selects formats satisfying ω = 3 log(r)/log(mnp) < log2 7 ≈ 2.807.
  • The table reports rank, coefficient ring, and resulting exponent for every qualifying format.
  • The 3 × 4 × 6 scheme was rediscovered with ZT coefficients, making its tensor-product 6 × 8 × 12 scheme available in ternary form.
Loading 2603.02398v1…