Alternative Basis matrix multiplication is fast and stable†

Abstract 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. Particularly, we derive a novel fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs, and achieves an improved asymptotic error bound. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously optimized. We provide high-performance parallel implementations of our algorithms with benchmarks showing that our algorithm is on par with the best in class for speed, and the best in class of 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.