Fast matrix multiplication is stable

DOI10.1007/S00211-007-0061-6MaRDI QIDQ879926zbMATHOpenAlexFDO

Authors James Demmel, Ioana Dumitriu, Olga Holtz, Robert D. Kleinberg

Publication date 10 May 2007

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603207

zbMATH Keywords

forward error analysisMatrix multiplicationgroup-theoretic algorithmsnumerically stable algorithms

Mathematics Subject Classification ID

Roundoff error (65G50)

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.

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

• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Accuracy and Stability of Numerical Algorithms
• Computational Complexity and Numerical Stability
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• Exploiting fast matrix multiplication within the level 3 BLAS
• Fast linear algebra is stable
• Fast multiplication of large numbers
• Gaussian elimination is not optimal
• LAPACK Users' Guide
• Matrix multiplication via arithmetic progressions
• On the Complexity of Matrix Product
• On the optimal evaluation of a set of bilinear forms
• ScaLAPACK Users' Guide
• Stability of block algorithms with fast level-3 BLAS
• Stability of fast algorithms for matrix multiplication
• The Cooley-Tukey FFT and group theory.

Cited in

(12)

• Improving the numerical stability of fast matrix multiplication
• Numerical stability and tensor nuclear norm
• Strassen's Algorithm for Tensor Contraction
• Fast matrix multiplication by using color algebras
• Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
• Analyzing group based matrix multiplication algorithms
• Fast linear algebra is stable
• Communication lower bounds and optimal algorithms for numerical linear algebra
• A bootstrap method for error estimation in randomized matrix multiplication
• A stable algorithm for matrix exponent calculation
• Fast matrix multiplication and its algebraic neighbourhood
• Fast structured matrix computations: tensor rank and Cohn-Umans method

Describes a project that uses

Uses Software

• LAPACK
• ScaLAPACK
• CLAPACK
• mctoolbox

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)