# Fast Matrix Multiplication via Ternary Meta Flip Graphs

Preprint · A. I. Perminov

- Archive id: arxiv:2511.20317
- Published: 2025-11-25
- arXiv: https://arxiv.org/abs/2511.20317
- Source URL: https://arxiv.org/abs/2511.20317
- PDF: https://arxiv.org/pdf/2511.20317
- Provenance: arxiv

## Abstract

Matrix multiplication optimization remains a fundamental challenge in computational mathematics. This work introduces a novel approach that discovers matrix multiplication schemes whose coefficients are restricted to the set $\\{-1, 0, 1\\}$ (denoted $Z\_T$), minimizing naive additive complexity for efficient hardware implementation. The core of the method is a GPU-accelerated meta flip graph algorithm that maintains ternary safety through specialized arithmetic operations and sign symmetry breaking. Key results include new best ranks for the formats $4 \\times 5 \\times 12$, $5 \\times 6 \\times 10$, and $6 \\times 7 \\times 9$, the independent discovery of 32 schemes in $Z\_T$ that match known optimal ranks (including 8 previously known only with rational coefficients), and 30 rank improvements in the binary field. The analysis of 164 known schemes shows that 92 admit a ternary-coefficient implementation, while 72 could not be found under this constraint, defining the current boundaries of the approach. All software, results, and discovered schemes are provided as open-source.

_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.