Search papers, labs, and topics across Lattice.
This paper introduces an open-source C++ framework for discovering fast matrix multiplication schemes using the flip graph approach across binary, modular ternary, and integer ternary coefficient rings. The framework employs bit-level encoding and OpenMP parallelism to enable large-scale exploration on commodity hardware, covering 680 schemes from $(2 \times 2 \times 2)$ to $(16 \times 16 \times 16)$. The study improves the multiplicative complexity for 79 matrix multiplication schemes, including a new $4 \times 4 \times 10$ scheme requiring only 115 multiplications, achieving $\omega \approx 2.80478$.
A new $4 \times 4 \times 10$ matrix multiplication scheme slashes the number of required multiplications to 115, beating Strassen's exponent for this size and pushing $\omega$ down to approximately 2.80478.
An open-source C++ framework for discovering fast matrix multiplication schemes using the flip graph approach is presented. The framework supports multiple coefficient rings -- binary ($\mathbb{Z}_2$), modular ternary ($\mathbb{Z}_3$) and integer ternary ($\mathbb{Z}_T = \{-1,0,1\}$) -- and implements both fixed-dimension and meta-dimensional search operators. Using efficient bit-level encoding of coefficient vectors and OpenMP parallelism, the tools enable large-scale exploration on commodity hardware. The study covers 680 schemes ranging from $(2 \times 2 \times 2)$ to $(16 \times 16 \times 16)$, with 276 schemes now in $\mathbb{Z}_T$ coefficients and 117 in integer coefficients. With this framework, the multiplicative complexity (rank) is improved for 79 matrix multiplication schemes. Notably, a new $4 \times 4 \times 10$ scheme requiring only 115 multiplications is discovered, achieving $\omega \approx 2.80478$ and beating Strassen's exponent for this specific size. Additionally, 93 schemes are rediscovered in ternary coefficients that were previously known only over rationals or integers, and 68 schemes in integer coefficients that previously required fractions. All tools and discovered schemes are made publicly available to enable reproducible research.
