  Fast algorithms for matrix multiplication, namely those that perform
asymptotically fewer scalar operations than the classical algorithm, have been
considered primarily of theoretical interest. Apart from Strassen's original
algorithm, few fast algorithms have been efficiently implemented or used in
practical applications. However, there exist many practical alternatives to
Strassen's algorithm with varying performance and numerical properties. Fast
algorithms are known to be numerically stable, but because their error bounds
are slightly weaker than the classical algorithm, they are not used even in
cases where they provide a performance benefit.
  We argue in this paper that the numerical sacrifice of fast algorithms,
particularly for the typical use cases of practical algorithms, is not
prohibitive, and we explore ways to improve the accuracy both theoretically and
empirically. The numerical accuracy of fast matrix multiplication depends on
properties of the algorithm and of the input matrices, and we consider both
contributions independently. We generalize and tighten previous error analyses
of fast algorithms and compare their properties. We discuss algorithmic
techniques for improving the error guarantees from two perspectives:
manipulating the algorithms, and reducing input anomalies by various forms of
diagonal scaling. Finally, we benchmark performance and demonstrate our
improved numerical accuracy.
