Hugo Nielsen

cs.DS — Data Structures and Algorithms

Improved basis-change transformations for $2 \times 2$ matrix multiplication

Contributed by Hugo Nielsen

To the best of our knowledge, we present a state-of-the-art change-of-basis algorithm for $2 \times 2$ matrix multiplication under the Karstadt--Schwartz-style basis change regime [1]. We do this by introducing basis-change matrices $B_U$, $B_V$, and $B_W$ that each require only a single addition and hence give rise to a matrix-multiplication algorithm performing $5n^{\log_2{7}} - 4n^2 + \frac{3}{4}n^2 \log_2{n},$ arithmetic operations when multiplying two $n \times n$ matrices, with $n$ a power of $2$. This improves on the previous best bound, which had last term $\frac{3}{2}n^2\log_2{n}$.