Fast matrix multiplication is stable

We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of Bini and Lotti Numer. Math. 36:63–72, 1980]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in Cohn and Umans Foundations of Computer Science, 44th Annual IEEE Symposium, pp. 438–449, 2003] and Cohn et al. Foundations of Computer Science, 46th Annual IEEE Symposium, pp. 379–388, 2005] are all included in the class of algorithms to which our analysis applies, and are therefore numerically stable. We perform detailed error analysis for three specific fast group-theoretic algorithms. J. Demmel acknowledges support of NSF under grants CCF-0444486, ACI-00090127, CNS-0325873 and of DOE under grant DE-FC02-01ER25478. I. Dumitriu acknowledges support of the Miller Institute for Basic Research in Science. R. Kleinberg is supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship