Fast matrix multiplication is stable
- Author(s): Demmel, James;
- Holtz, Olga;
- Kleinberg, Robert;
- Dumitriu, Ioana
- et al.
Published Web Locationhttp://www.springerlink.com/content/w7158p34v2248073/
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.