Fast linear algebra is stable

DOI10.1007/S00211-007-0114-XMaRDI QIDQ2461610zbMATH OpenOpenAlexDBLPWikidataFDO

Authors James Demmel, Ioana Dumitriu, Olga Holtz

Publication date 28 November 2007

Published in Numerische Mathematik (Search for Journal in Brave)

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

zbMATH Keywords

fast algorithmsingular value decompositionstabilitycomplexityeigenvaluelinear equationmatrix multiplicationdeterminantsleast squares problemsmatrix inversionQR decompositionLU decompositiondivide-and-conquer algorithmsRRURV decompositionstandard linear algebra operation

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical linear algebra (65Fxx)

Abstract: In an earlier paper, we showed that a large class of fast recursive matrix multiplication algorithms is stable in a normwise sense, and that in fact if multiplication of $n$-by-$n$ matrices can be done by any algorithm in $O(n^{omega+eta})$ operations for any $eta>0$, then it can be done stably in $O(n^{omega+eta})$ operations for any $eta>0$. Here we extend this result to show that essentially all standard linear algebra operations, including LU decomposition, QR decomposition, linear equation solving, matrix inversion, solving least squares problems, (generalized) eigenvalue problems and the singular value decomposition can also be done stably (in a normwise sense) in $O(n^{omega+eta})$ operations.

Recommendations

• New Fast and Accurate Jacobi SVD Algorithm. I
• Fast matrix multiplication is stable
• scientific article; zbMATH DE number 1304510
• Fast rectangular matrix multiplication and QR decomposition
• Stability of block algorithms with fast level-3 BLAS

Cites work

• scientific article; zbMATH DE number 3886886 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A Storage-Efficient WY Representation for Products of Householder Transformations
• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Accuracy and Stability of Numerical Algorithms
• Circular dichotomy of the matrix spectrum
• Computing invariant subspaces of a regular linear pencil of matrices
• Computing rank-revealing QR factorizations of dense matrices
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Eigenvalues and Condition Numbers of Random Matrices
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• Exploiting fast matrix multiplication within the level 3 BLAS
• Fast matrix multiplication is stable
• Fast multiplication of large numbers
• Gaussian elimination is not optimal
• Generation of Random Orthogonal Matrices
• LAPACK Users' Guide
• Linear model reduction and solution of the algebraic Riccati equation by use of the sign function†
• Locality of Reference in LU Decomposition with Partial Pivoting
• Matrix multiplication via arithmetic progressions
• On Rank-Revealing Factorisations
• On the Complexity of Matrix Product
• On the Separation of Two Matrices
• Parallel algorithm for solving some spectral problems of linear algebra
• Parallel spectral division using the matrix sign function for the generalized eigenproblem
• Problem of the dichotomy of the spectrum of a matrix
• Rang revealing QR factorizations
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• ScaLAPACK Users' Guide
• Stability of Parallel Triangular System Solvers
• Stability of block LU factorization
• Stability of block algorithms with fast level-3 BLAS
• Stability of fast algorithms for matrix multiplication
• The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
• The WY Representation for Products of Householder Matrices
• Updating a Rank-Revealing ULV Decomposition
• Using the Matrix Sign Function to Compute Invariant Subspaces

Cited in

(47)

• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• Realizing Euclidean distance matrices by sphere intersection
• Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD
• Predicting state transitions in brain dynamics through spectral difference of phase-space graphs
• A low-complexity algorithm to search for Legendre pairs
• Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• Randomized low-rank approximations beyond Gaussian random matrices
• Statistical Analysis of Random Objects Via Metric Measure Laplacians
• Numerical stability and tensor nuclear norm
• Fast matrix multiplication and its algebraic neighbourhood
• Randomized numerical linear algebra: Foundations and algorithms
• Derivative transfer matrix method: machine precision calculation of electron structure and interface phonon dispersion in semiconductor heterostructures
• Strassen's algorithm is not optimally accurate
• Gonality of expander graphs
• Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
• Fast matrix multiplication is stable
• Stable solutions of linear systems involving long chain of matrix multiplications
• Complete equitable decompositions
• Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
• Practical sketching algorithms for low-rank matrix approximation
• Generalized pseudospectral shattering and inverse-free matrix pencil diagonalization
• Computing the asymptotic distribution of second-order \(U\)- and \(V\)-statistics
• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
• The Complexity of Diagonalization
• When can forward stable algorithms be composed stably?
• A quasi-random approach to matrix spectral analysis
• Fast and inverse-free algorithms for deflating subspaces
• Pebbling Game and Alternative Basis for High Performance Matrix Multiplication
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Alternative basis matrix multiplication is fast and \(\mathrm{stable}^\dag\)
• Transition probability of Brownian motion in the octant and its application to default modelling
• Solving sparse linear systems faster than matrix multiplication
• The bit complexity of dynamic algebraic formulas and their determinants
• A probabilistic diagnostic for Laplace approximations: introduction and experimentation
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Self-triggered output-feedback control of LTI systems subject to disturbances and noise
• Duality of matrix pencils, Wong chains and linearizations
• Fine-grained analysis and faster algorithms for iteratively solving linear systems
• Towards automated generation of fast and accurate algorithms for recursive matrix multiplication
• Rounding error analysis of mixed precision block Householder QR algorithms
• The impact of data distribution in accuracy and performance of parallel linear algebra subroutines
• Improving the numerical stability of fast matrix multiplication
• On the computation of general vector-valued modular forms
• Modified ST algorithms and numerical experiments
• A search-based procedure for nonlinear real arithmetic
• Smallest eigenvalue distributions for two classes of {\(\beta\)}-Jacobi ensembles

Describes a project that uses

Uses Software

• mctoolbox
• CLAPACK
• ScaLAPACK
• LAPACK

This page was built for publication: Fast linear algebra is stable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461610)