# Fast matrix multiplication is stable

Article · James Demmel, Ioana Dumitriu, Olga Holtz, Robert Kleinberg

- Archive id: arxiv:math/0603207
- Published: 2006-03-09
- Venue: Numer. Math. 106 (2007), no. 2, 199-224
- DOI: https://doi.org/10.1007/s00211-007-0061-6
- arXiv: https://arxiv.org/abs/math/0603207
- Citations: 77
- Source URL: https://arxiv.org/abs/math/0603207
- PDF: https://arxiv.org/pdf/math/0603207
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.