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

complexitydeterminantsdivide-and-conquer algorithmseigenvaluefast algorithmleast squares problemslinear equationLU decompositionmatrix inversionmatrix multiplicationQR decompositionRRURV decompositionsingular value decompositionstabilitystandard linear algebra operation

Mathematics Subject Classification ID

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

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.

Review text

This is an important development of the work by \textit{J. Demmel}, \textit{I. Dumitriu}, \textit{O. Holtz} and \textit{R. Kleinberg} [Numer. Math. 106, No. 2, 199--224 (2007; Zbl 1134.65030)]. It is shown that essentially all standard linear algebra operations, including LU decomposition, QR decomposition, linear equation solving, matrix inversion, solving least squares problems, eigenvalue problems and the singular value decomposition can be done stably by fast algorithms. Briefly, the vein of this work is: By considering known divide-and-conquer algorithms the complexity of matrix inversion is reduced to the complexity of matrix multiplication. A divide-and-conquer algorithm for QR decomposition is analysed, and is in turn used to solve linear systems, least squares problems, and to compute determinants equally fast and stable. The same idea is applied to LU decomposition. The results on QR decomposition are then applied to analyse the RRURV decomposition of a matrix, to compute the Schur form and the singular value decomposition.

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

• 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
• 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?)
• 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 block LU factorization
• Stability of block algorithms with fast level-3 BLAS
• Stability of fast algorithms for matrix multiplication
• Stability of Parallel Triangular System Solvers
• 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

(50)

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

Describes a project that uses

Uses Software

• mctoolbox
• LAPACK
• ScaLAPACK
• CLAPACK

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)