Fast matrix multiplication is stable
<|reference_start|>Fast matrix multiplication is stable: We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of [D. Bini and G. Lotti, Stability of fast algorithms for matrix multiplication, Numer. Math. 36 (1980), 63--72]. 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 [H. Cohn, and C. Umans, A group-theoretic approach to fast matrix multiplication, FOCS 2003, 438--449] and [H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic algorithms for matrix multiplication, FOCS 2005, 379--388] 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.<|reference_end|>
@article{demmel2006fast,
    title={Fast matrix multiplication is stable},
    author={James Demmel, Ioana Dumitriu, Olga Holtz, Robert Kleinberg},
    journal={Numer. Math. 106 (2007), no. 2, 199-224},
    year={2006},
    doi={10.1007/s00211-007-0061-6},
    archivePrefix={arXiv},
    eprint={math/0603207},
    primaryClass={math.NA cs.CC cs.DS math.GR}
}