Complex to Rational Fast Matrix Multiplication
2026-02-13 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study ways to speed up matrix multiplication, which is often slow in practice due to using complicated complex numbers. They develop a clear method to turn these complex-number-based multiplication schemes into ones using only real or rational numbers, or to prove when this is impossible. Their method builds on basic ideas from linear algebra and improves on earlier results by other researchers. They apply this method to show that some known algorithms can't be converted to simpler number systems. Overall, their work helps understand the limits of simplifying fast matrix multiplication methods.
matrix multiplicationcomplex coefficientsrational coefficientslinear algebrasimilarity transformationsalgorithm equivalencefast matrix multiplicationsquare rootsSmirnov algorithmKaporin algorithm
Authors
Yoav Moran, Oded Schwartz, Shuncheng Yuan
Abstract
Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case. Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes.