Fast matrix multiplication is stable
From MaRDI portal
Publication:879926
DOI10.1007/S00211-007-0061-6zbMATH Open1134.65030arXivmath/0603207OpenAlexW2147348850MaRDI QIDQ879926FDOQ879926
Authors: James Demmel, Ioana Dumitriu, Olga Holtz, Robert D. Kleinberg 
Publication date: 10 May 2007
Published in: Numerische Mathematik (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/0603207
Recommendations
- Improving the numerical stability of fast matrix multiplication
- Fast linear algebra is stable
- Matrix multiplication, a little faster
- Fast Output-Sensitive Matrix Multiplication
- Fast interval matrix multiplication
- Fast rectangular matrix multiplication and applications
- Fast matrix multiplication and its algebraic neighbourhood
- A practical algorithm for faster matrix multiplication
- Fast rectangular matrix multiplication and some applications
- scientific article; zbMATH DE number 3940617
Cites Work
- LAPACK Users' Guide
- ScaLAPACK Users' Guide
- Gaussian elimination is not optimal
- Fast multiplication of large numbers
- Title not available (Why is that?)
- Accuracy and Stability of Numerical Algorithms
- Matrix multiplication via arithmetic progressions
- On the Complexity of Matrix Product
- Stability of block algorithms with fast level-3 BLAS
- Exploiting fast matrix multiplication within the level 3 BLAS
- Fast linear algebra is stable
- Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
- Computational Complexity and Numerical Stability
- Stability of fast algorithms for matrix multiplication
- The Cooley-Tukey FFT and group theory.
- On the optimal evaluation of a set of bilinear forms
Cited In (11)
- Analyzing group based matrix multiplication algorithms
- Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
- A bootstrap method for error estimation in randomized matrix multiplication
- Fast matrix multiplication and its algebraic neighbourhood
- Fast linear algebra is stable
- Fast structured matrix computations: tensor rank and Cohn-Umans method
- Strassen's Algorithm for Tensor Contraction
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Fast matrix multiplication by using color algebras
- Improving the numerical stability of fast matrix multiplication
- A stable algorithm for matrix exponent calculation
Uses Software
This page was built for publication: Fast matrix multiplication is stable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879926)
