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

Preprint · Zeke Medley, Anagha Gokul, Quan Luu, Panagiotis Manolios

- Archive id: arxiv:2609.17533
- Published: 2026-06-22
- arXiv: https://arxiv.org/abs/2609.17533
- Source URL: https://arxiv.org/abs/2609.17533
- PDF: https://arxiv.org/pdf/2609.17533
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.