Fast matrix multiplication is stable
arXiv:math/0603207 · doi:10.1007/s00211-007-0061-6
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.
19 pages; final version, expanded and updated to reflect referees' remarks; to appear in Numerische Mathematik
References in corpus (3)
Cited by in corpus (20)
- Fast linear algebra is stable
- Simple and Tighter Derivation of Achievability for Classical Communication over Quantum Channels
- Entanglement of formation of mixed many-body quantum states via Tree Tensor Operators
- Fast Feasible and Unfeasible Matrix Multiplication
- Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
- Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs
- Implementing Strassen's Algorithm with BLIS
- Approximate multiplication of nearly sparse matrices with decay in a fully recursive distributed task-based parallel framework
- Solving Sparse Linear Systems Faster than Matrix Multiplication
- A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication
- Fast structured matrix computations: tensor rank and Cohn--Umans method
- Randomization of Approximate Bilinear Computation for Matrix Multiplication
- Computational Complexity and Numerical Stability of Linear Problems
- Horner Systems: How to efficiently evaluate non-commutative polynomials (by matrices)
- Generating Families of Practical Fast Matrix Multiplication Algorithms
- Strassen's Algorithm for Tensor Contraction
- Fast and Inverse-Free Algorithms for Deflating Subspaces
- A Heterogeneous Accelerated Matrix Multiplication: OpenCL + APU + GPU+ Fast Matrix Multiply
- Group-theoretic Methods for Bounding the Exponent of Matrix Multiplication
- Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision