2025/11/25 by Perminov, A. I. · 1 citation
Computer Science · Mathematics · #Polynomial and algebraic computation #Cryptography and Residue Arithmetic #Tensor decomposition and applications
paper · doi:10.48550/arxiv.2511.20317
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 ZT), 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 × 5 × 12, 5 × 6 × 10, and 6 × 7 × 9, the independent discovery of 32 schemes in ZT 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.