Source-linked AI summary
GPU-Accelerated Search for Fast Matrix Multiplication over $\mathbb{F}_2$
Zeke Medley, Anagha Gokul, Quan Luu, Panagiotis Manolios
TL;DR
The paper addresses the search for matrix multiplication algorithms using few scalar multiplications by developing a GPU-accelerated search over the matrix multiplication flip graph. It also proves flip-plus strong connectivity over F2 and finds a 245-multiplication algorithm for 7 × 7 matrix multiplication, improving the previous record by three multiplications.
Problem
Finding matrix multiplication schemes with few scalar multiplications requires efficient exploration of the matrix multiplication flip graph.
Method
The paper uses GPU warp-level matching primitives and generalized multi-summand flips for flip-graph search, alongside a flip-plus connectivity proof over F2.
Results
245 multiplications multiply 7 × 7 matrices over F2, improving the previous best known rank by three multiplications; the implementation explores over a billion vertices per second on an NVIDIA H200.
Takeaways & Limitations
Flip and plus transformations suffice for strong connectivity over F2, while the GPU procedure substantially improves flip-graph search throughput.
Takeaways & Limitations
The evaluation does not compare GPU search with CPU search under a fixed hardware-rental cost, and the best search-round parameter remains understudied across settings.
Abstract
from arXiv · showhide
We present a GPU-accelerated algorithm for searching for ways to multiply matrices with few scalar multiplications. Our algorithm searches the matrix multiplication flip graph and, on an NVIDIA H200, performs over a billion search steps per second, a $1000\times$ improvement over previous GPU-accelerated search on the tensor for $7\times7$ matrix multiplication. Our second contribution is a proof that, over $\mathbb{F}_2$, the directed matrix multiplication flip graph is strongly connected with only flip and plus edges. This removes the need for computationally expensive reduction edges in the connectivity argument used in previous work. Using this GPU-accelerated search procedure on our simplified flip graph, we find a way to multiply $7\times 7$ matrices over $\mathbb{F}_2$ using 245 multiplications, a three-multiplication improvement over the previous record.
1 Introduction
The paper develops a GPU-oriented flip-graph search method for finding low-multiplication matrix algorithms and combines it with theoretical and empirical advances.
- 1 Introduction: GPU hardware-supported matching replaces large-map queries for finding triples sharing a value in one position.This targets the massive parallelism available in modern GPUs.
- 1 Introduction: Over a billion vertices per second and over 1000× faster than previous GPU search are achieved on the 7 × 7 flip graph using an NVIDIA H200.The algorithm uses warp-level matching primitives to detect flip opportunities.
- 1 Introduction: Generalized multi-summand flips discover the record 4×4 scheme 1.66× as fast as an implementation without them.They exploit linear dependencies among summands sharing a tensor factor and expose rank reductions efficiently on GPUs.
- 1 Introduction: Over F2, ordinary flip and plus edges alone strongly connect the directed flip graph, eliminating computationally expensive reduction edges from the connectivity argument.
- 1 Introduction: 245 multiplications multiply 7 × 7 matrices over F2, improving the previous record by three multiplications.
2 Related Work
Prior work established flip-graph search, connectivity extensions, symmetry variants, and GPU implementations; this paper focuses on simplifying connectivity over F2.
- 2 Related Work: Earlier connectivity work used flip or reduction transforms, while later work added plus transitions to improve connectivity and escape local minima.
- 2 Related Work: Symmetry-constrained flip graphs reduce the explorable graph but sacrifice completeness because non-symmetric schemes become unreachable.
- 2 Related Work: Prior research extended flip-graph search to commutative, structured, and cross-format matrix multiplication, and introduced GPU acceleration.
- 2 Related Work: Over F2, reduction edges may be unnecessary because searches already operate over F2 and reductions are rare and slow; Theorem 3.4 confirms this.
3 Preliminaries
The preliminaries define matrix multiplication tensors, rank decompositions, schemes, and the flip graph, then state the paper’s flip-plus connectivity theorem over F2.
- 3 Preliminaries: The matrix multiplication tensor records which products of entries from two input matrices contribute to each entry of their product.
- 3 Preliminaries: A rank-R decomposition of the matrix multiplication tensor gives a matrix-multiplication algorithm using R scalar multiplications, so the goal is a low-rank decomposition.
- 3 Preliminaries: A scheme is a multiset of nonzero rank-one tensors satisfying the matrix multiplication tensor equation, and its size is its rank.
- 3 Preliminaries: Flip-graph vertices are schemes, with directed edges given by flip or plus transformations between transformable schemes.Zero summands are deleted, and the transformations preserve the represented tensor.
- 3 Preliminaries: For every n ≥ 2 over F2, the directed flip graph using only ordinary flip and plus transformations is strongly connected.Thus every scheme can reach every other scheme through those transformations.
4 Connectivity Proof
The proof establishes strong connectivity over F2 using only flip and plus edges. It builds paths by adding duplicate summands, decomposing zero-summing submultisets, and deleting identical pairs.
- Proof strategy: The proof follows Arai et al.’s connectivity strategy but exploits F2-specific structure to remove zero-summing submultisets without computationally expensive reduction edges.The argument assumes n ≥ 2, the regime relevant to matrix multiplication search.
- Cancellation over F2: Over F2, identical summands cancel in pairs through a flip, enabling duplicate deletion without reduction edges.Two identical summands produce zero summands after a flip and are then deleted.
- Local transformation: Lemma 4.4 changes a pair of summands through plus operations and a final flip, restoring the originals while adding two copies of X ⊗ B ⊗ C.The same construction handles both B ≠ B′ and B = B′, with analogous statements for the other component positions.
- Adding duplicate tensors: Lemma 4.5 adds two copies of any nonzero tensor X ⊗ Y ⊗ Z by changing components successively from existing summands to the target components.The construction uses spanning component sets, nonzero partial sums, Lemma 4.4, and duplicate-pair deletion.
- Removing zero-summing submultisets: Lemma 4.6 removes any zero-summing submultiset using only flip and plus edges by decomposing its summands into standard basis tensors.The resulting basis tensors occur with even multiplicity over F2, so equal pairs can be deleted.
- Main theorem: Theorem 3.4 proves that any scheme S can reach any scheme S′ using only flip and plus edges, so the directed graph is strongly connected.The path first adds two copies of every summand of S′, then removes the zero-summing submultiset S ⊎ S′.
5 GPU-Accelerated Search
The search procedure replaces GPU-unfriendly hash-map detection with warp-local matching and extends flips to generalized multi-summand operations. These generalized flips efficiently expose rank reductions while remaining paths in the ordinary flip graph.
- 5.1 Search Procedure: GPU search identifies flip opportunities with warp-local matching primitives instead of branchy hash tables and shared-memory maps.Each thread stores summands and match any sync produces bitmasks for equal A, B, or C values; with multiple summands per thread, repeated random sampling makes discovery probabilistic.
- 5.2 Generalized Flips: Generalized flips can skip ahead to rank reductions by applying an invertible change of basis to linearly dependent non-shared factors.A suitable transformation can create zero B- or C-factors, corresponding to rank reductions that may otherwise require many pairwise flip and plus transforms.
- 5.2 Generalized Flips: 99.93% of 43,386 multi-summand sharing sets from 3,273 sampled 5 × 5 schemes had size at most 5, fitting nonempty-subset testing into a 32-thread warp.For groups of at most five summands, linear dependence over F2 can be tested by checking whether a nonempty subset XORs to zero.
- 5.2 Generalized Flips: A generalized flip is a path in the ordinary flip graph realizable with O(N^2) pairwise flips.Elementary column additions implement the required basis transformations, and Gaussian elimination expresses any invertible transformation using O(N^2) such additions.
- 5.3 Rank Reduction of Generalized Flips: The optimal generalized flip on a group sharing one factor leaves exactly rank(TBC) non-zero surviving summands.The construction achieves the lower bound, and analogous statements hold for groups sharing the B or C factor.
6 Evaluation
The evaluation shows substantially faster GPU flip-graph exploration than prior GPU search, with corresponding rank reductions, while noting unresolved evaluation gaps.
- Evaluation limitations: The evaluation leaves open how the number of search rounds k should be chosen across start locations and matrix sizes, and lacks a cost-controlled GPU–CPU comparison.The authors also note that CPU implementations explore around 50M vertices per second and that an H200 may cost as much as many CPUs.
- Throughput comparison: 4–21,000× more flip-graph vertices per second than Perminov’s GPU procedure were visited for matrix sizes from 3 × 3 to 8 × 8.The comparison used the NVIDIA H200 and is shown in Figure 3.
7 Conclusion
The conclusion combines a GPU-oriented flip-graph search procedure with generalized flips and a simplified binary connectivity result. Experiments exceed a billion explored vertices per second and produce a rank-245 7 × 7 × 7 decomposition, improving the prior best by three multiplications.
- GPU search procedure: Warp-local matching operations replace global data structures for detecting flip opportunities, making flip-graph random walks better suited to modern GPUs.The search procedure is GPU-accelerated and uses generalized multi-summand flips as GPU-efficient macro-edges.
- Connectivity result: Over F2, ordinary flip and plus transformations suffice to strongly connect the directed matrix multiplication flip graph, eliminating reduction edges from the connectivity argument.This theoretical simplification applies specifically in the binary setting.
- Experimental results: Rank 245 for the 7 × 7 × 7 matrix multiplication tensor over F2 improves the previous best known rank by three multiplications.The decomposition was found using the proposed search procedure.
- Experimental results: Over a billion vertices per second are explored on an NVIDIA H200, substantially exceeding previous GPU-accelerated flip-graph search throughput.The conclusion reports this as the implementation’s experimental throughput result.
A The Scheme
The appendix encodes a rank-245 decomposition of the 7 × 7 × 7 matrix multiplication tensor over F2 and provides a verifier that decodes and checks it.
- Scheme encoding: The scheme is stored as compressed Base32 data containing three seven-byte binary coefficient masks for each of 245 rank-one terms.The masks are ordered A, B, C, with bit 7i + j recording matrix coordinate [i, j].
- Structural checks: The verifier converts each mask into its supported coordinates and rejects rank-one terms containing a zero factor or an unexpected number of terms.These checks validate the structural representation before tensor verification.
- Tensor verification: It verifies correctness by comparing parity contributions from the decoded terms with all expected triples (iN + j, jN + k, iN + k).For N = 7, successful verification prints that the rank-245 decomposition represents M^(7) over F2.