{"id":"arxiv:2511.20317","kind":"preprint","title":"Fast Matrix Multiplication via Ternary Meta Flip Graphs","authors":["A. I. Perminov"],"author_count":1,"year":2025,"published":"2025-11-25","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2511.20317","nct_id":null,"source_url":"https://arxiv.org/abs/2511.20317","archive_url":"https://space-kitty.com/papers/arxiv:2511.20317","updated":"2025-11-29","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2511.20317","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.SC","cs.DS"],"details":null,"provenance":"arxiv","attribution":"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.","topics":[],"cited_in_dossiers":[]}