Alternative Basis Matrix Multiplication is Fast and Stable
Oded Schwartz, Sivan Toledo, Noa Vaknin, Gal Wiernik · 2024
Alternative basis matrix multiplication algorithms are the fastest matrix multiplication algorithms in practice to date. However, are they numerically stable?We obtain the first numerical error bound for alternative basis matrix multiplication algorithms, demonstrating that their error bounds are asymptotically identical to the standard fast matrix multiplication algorithms, such as Strassen’s. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously and independently optimized. Particularly, we obtain the first fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs and optimal asymptotic error bound, effectively beating the Bini and Lotti (1980) speed-stability trade-off for fast matrix multiplication. We provide high-performance parallel implementations of our algorithms with benchmarks that show our algorithm is on par with the best in class for speed and with the best in class for stability. Finally, we show that diagonal scaling stability improvement techniques for fast matrix multiplication are as effective for alternative basis algorithms, both theoretically and empirically. These findings promote the use of alternative basis matrix multiplication algorithms in practical applications.