{"ID":2836972,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.20317","arxiv_id":"2511.20317","title":"Fast Matrix Multiplication via Ternary Meta Flip Graphs","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.","short_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 imp...","url_abs":"https://arxiv.org/abs/2511.20317","url_pdf":"https://arxiv.org/pdf/2511.20317v2","authors":"[\"A. I. Perminov\"]","published":"2025-11-25T13:53:17Z","proceeding":"cs.SC","tasks":"[\"cs.SC\",\"cs.DS\"]","methods":"[]","has_code":false}