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

Abstract

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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.