Fast linear algebra is stable

By J. Demmel, Ioana Dumitriu, Olga Holtz. 2006

265 citations recorded by the source corpus.

In Demmel et al. (Numer. Math. 106(2), 199–224, 2007) 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ω+η) operations for any η > 0, then it can be done stably in O(nω+η) operations for any η > 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ω+η) operations.

Subfields: Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “However, either the proximity matrix construction or the eigendecomposition of the matrix is time and space consuming [149], making matrix factorization inefficient and unscalable for large graphs.”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, methodology): “Here we state the consequences of plugging our OSE’s into known previous work for various numerical linear algebra problems [8], [9], [11], [12], [14], [15], [22].”
Communication-optimal Parallel and Sequential QR and LU Factorizations (2008, methodology): “rations only depend on these columns eliminates algorithms like Strassen. (It is known that QR can be done asymptotically as fast as any fast matrix multiplication algorithm like Strassen, and stably [15].) This section says where the lower bound on F comes from that is used in the proof of Corollar”
Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms (2011, methodology): “As an alternative, we are also looking into adjusting the algorithms for computing QR, eigenvalue decompositions, and the SVD which use Strassen’s algorithm [10] to using our 2.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “3) is rank-revealing in theory (see Demmel et al. (2007, Theorem 5.2) and Ballard, Demmel, Dumitriu and Rusciano (2019)), but it does not reveal the rank particularly well in practice.”
Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD (2013, methodology): “The algorithms of Bai, Demmel, and Gu [8] and Demmel, Dumitriu, and Holtz [16] all have the same basic structure of first mapping the eigenvalues to 0 or ∞ by an implicit repeated squaring of the eigenvalues [8, Sec.”
Mathematicians of Gaussian Elimination (2011, background): “More radical transformations are possible that reduce the work to solve n equations below O(n3) arithmetic operations [Strassen, 1969; Cohn and Umans, 2003; Demmel et al., 2007].”