Fast linear algebra is stable

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.

26 pages; final version; to appear in Numerische Mathematik

References in corpus (3)

• Group-theoretic algorithms for matrix multiplication
• Fast matrix multiplication is stable
• A group-theoretic approach to fast matrix multiplication

Cited by in corpus (22)

• Minimizing Communication in Linear Algebra
• Practical sketching algorithms for low-rank matrix approximation
• Fast matrix multiplication is stable
• A generalization of Bloch's theorem for arbitrary boundary conditions: Theory
• Randomized resolvent analysis
• General expressions for the quantum Fisher information matrix with applications to discrete quantum imaging
• Inferring the three-dimensional distribution of dust in the Galaxy with a non-parametric method: Preparing for Gaia
• Efficient classical algorithms for simulating symmetric quantum systems
• Efficient online quantum state estimation using a matrix-exponentiated gradient method
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• Classical and Quantum Algorithms for Tensor Principal Component Analysis
• KAISA: An Adaptive Second-Order Optimizer Framework for Deep Neural Networks
• Partially Unitary Learning
• QUINT: Node embedding using network hashing
• Approximation and bounding techniques for the Fisher-Rao distances between parametric statistical models
• Efficient Time-Series Approximation with Linear Recurrent Neural Networks: Architecture Learning and Predictive Power
• Generalized Pseudospectral Shattering and Inverse-Free Matrix Pencil Diagonalization
• Randomization of Approximate Bilinear Computation for Matrix Multiplication
• Maximum expectation of observables with restricted purity states
• Introducing UNIQuE: The Unconventional Noiseless Intermediate Quantum Emulator
• Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
• Fast and Inverse-Free Algorithms for Deflating Subspaces