Fast linear algebra is stable

DOI10.1007/S00211-007-0114-XzbMath1133.65015DBLPjournals/nm/DemmelDH07arXivmath/0612264OpenAlexW3099472489WikidataQ57311535 ScholiaQ57311535MaRDI QIDQ2461610

James W. Demmel, Ioana Dumitriu, O. V. 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

complexitystabilityeigenvaluesingular value decompositiondeterminantslinear equationfast algorithmQR decompositionleast squares problemsmatrix inversionmatrix multiplicationLU decompositiondivide-and-conquer algorithmsRRURV decompositionstandard linear algebra operation

Mathematics Subject Classification ID

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

Related Items (28)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Randomized algorithms for distributed computation of principal component analysis and singular value decomposition ⋮ Computing the asymptotic distribution of second-order \(U\)- and \(V\)-statistics ⋮ Fast matrix multiplication is stable ⋮ Predicting state transitions in brain dynamics through spectral difference of phase-space graphs ⋮ The Complexity of Diagonalization ⋮ Unnamed Item ⋮ 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 ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time ⋮ Statistical Analysis of Random Objects Via Metric Measure Laplacians ⋮ Self-triggered output-feedback control of LTI systems subject to disturbances and noise ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Realizing Euclidean distance matrices by sphere intersection ⋮ A search-based procedure for nonlinear real arithmetic ⋮ Duality of matrix pencils, Wong chains and linearizations ⋮ Transition Probability of Brownian Motion in the Octant and its Application to Default Modelling ⋮ Communication lower bounds and optimal algorithms for numerical linear algebra ⋮ Gonality of expander graphs ⋮ Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic ⋮ The Impact of Data Distribution in Accuracy and Performance of Parallel Linear Algebra Subroutines ⋮ Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations ⋮ Improving the Numerical Stability of Fast Matrix Multiplication ⋮ Rounding Error Analysis of Mixed Precision Block Householder QR Algorithms ⋮ Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD ⋮ Smallest eigenvalue distributions for two classes of β-Jacobi ensembles

Uses Software

• Unnamed Item
• Unnamed Item
• CLAPACK
• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rang revealing QR factorizations
• Fast matrix multiplication is stable
• Computing invariant subspaces of a regular linear pencil of matrices
• Matrix multiplication via arithmetic progressions
• Problem of the dichotomy of the spectrum of a matrix
• Circular dichotomy of the matrix spectrum
• Stability of fast algorithms for matrix multiplication
• Parallel algorithm for solving some spectral problems of linear algebra
• Gaussian elimination is not optimal
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• Fast multiplication of large numbers
• PARALLEL SPECTRAL DIVISION USING THE MATRIX SIGN FUNCTION FOR THE GENERALIZED EIGENPROBLEM
• The WY Representation for Products of Householder Matrices
• Generation of Random Orthogonal Matrices
• A Storage-Efficient $WY$ Representation for Products of Householder Transformations
• Eigenvalues and Condition Numbers of Random Matrices
• LAPACK Users' Guide
• On the Separation of Two Matrices
• The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
• Linear model reduction and solution of the algebraic Riccati equation by use of the sign function†
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Computing rank-revealing QR factorizations of dense matrices
• On Rank-Revealing Factorisations
• ScaLAPACK Users' Guide
• Exploiting fast matrix multiplication within the level 3 BLAS
• Stability of block algorithms with fast level-3 BLAS
• Locality of Reference in LU Decomposition with Partial Pivoting
• Using the Matrix Sign Function to Compute Invariant Subspaces
• On the Complexity of Matrix Product
• Stability of Parallel Triangular System Solvers
• Accuracy and Stability of Numerical Algorithms
• Stability of block LU factorization
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Updating a Rank-Revealing ULV Decomposition

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