arXiv:2609.17533 · v2

GPU-Accelerated Search for Fast Matrix Multiplication over $\mathbb{F}_2$

首次提交 2026-06-23 03:59

版本更新 2026-10-27 06:02

雷达观测 2026-10-29 00:35

摘要

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 for matrix sizes up to $7\times7$, a roughly $380\times$ improvement over previous GPU-accelerated search on the tensor for $7\times7$ matrix multiplication. We also prove 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 by 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.