Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices

DOI10.1137/18M1218212MaRDI QIDQ5220401zbMATH OpenFDO

Authors Takeshi Fukaya, Ramaseshan Kannan, Yuji Nakatsukasa, Yusaku Yamamoto, Yuka Yanagisawa

Publication date 20 March 2020

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Cholesky QR factorizationcommunication-avoiding algorithmsoblique inner productQR factorizationroundoff error analysis

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Ill-posedness and regularization problems in numerical linear algebra (65F22) Roundoff error (65G50)

Abstract: The Cholesky QR algorithm is an efficient communication-minimizing algorithm for computing the QR factorization of a tall-skinny matrix. Unfortunately it has the inherent numerical instability and breakdown when the matrix is ill-conditioned. A recent work establishes that the instability can be cured by repeating the algorithm twice (called CholeskyQR2). However, the applicability of CholeskyQR2 is still limited by the requirement that the Cholesky factorization of the Gram matrix runs to completion, which means it does not always work for matrices $X$ with $$ where $$ is the unit roundoff. In this work we extend the applicability to $$ by introducing a shift to the computed Gram matrix so as to guarantee the Cholesky factorization $R^{T}R=A^{T}A+sI$ succeeds numerically. We show that the computed $A{R}^{-1}$ has reduced condition number $$, for which CholeskyQR2 safely computes the QR factorization, yielding a computed $Q$ of orthogonality $|Q^{T}Q-I{|}_2$ and residual $|A-QR{|}_F/|A{|}_F$ both $$. Thus we obtain the required QR factorization by essentially running Cholesky QR thrice. We extensively analyze the resulting algorithm shiftedCholeskyQR to reveal its excellent numerical stability. shiftedCholeskyQR is also highly parallelizable, and applicable and effective also when working in an oblique inner product space. We illustrate our findings through experiments, in which we achieve significant (up to x40) speedup over alternative methods.

Recommendations

• Roundoff error analysis of the CholeskyQR2 algorithm
• Roundoff error analysis of the CholeskyQR2 algorithm in an oblique inner product
• Cholesky and Gram-Schmidt orthogonalization for tall-and-skinny QR factorizations on graphics processors
• Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs
• Publication:3212189

Cites work

• A Block Orthogonalization Procedure with Constant Synchronization Requirements
• Accuracy and Stability of Numerical Algorithms
• Communication-optimal parallel and sequential QR and LU factorizations
• Convergence analysis of an algorithm for accurate inverse Cholesky factorization
• Efficient implementations of the modified Gram-Schmidt orthogonalization with a non-standard inner product
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Iteratively reweighted least squares minimization for sparse recovery
• Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs
• Numerical stability of orthogonalization methods with a non-standard inner product
• Rounding error analysis of the classical Gram-Schmidt orthogonalization process
• Roundoff error analysis of the CholeskyQR2 algorithm
• Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices
• Super-fast validated solution of linear systems
• Templates for the Solution of Algebraic Eigenvalue Problems
• The University of Florida sparse matrix collection
• Very large electronic structure calculations using an out-of-core filter-diagonalization method

Cited in

(19)

• Block Gram-Schmidt algorithms and their stability properties
• Roundoff error analysis of the CholeskyQR2 algorithm in an oblique inner product
• Cholesky and Gram-Schmidt orthogonalization for tall-and-skinny QR factorizations on graphics processors
• The stability of block variants of classical Gram-Schmidt
• Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices
• Exploiting lower precision arithmetic in solving symmetric positive definite linear systems and least squares problems
• Mixed precision algorithms in numerical linear algebra
• Householder Orthogonalization with a Nonstandard Inner Product
• Exact QR factorizations of rectangular matrices
• Roundoff-error-free QR factorization via integer-preserving Gram Schmidt orthogonalization
• Analysis of randomized Householder-Cholesky QR factorization with multisketching
• An improved shifted CholeskyQR based on columns
• CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
• Distributed-parallel proper orthogonal/dynamic mode decompositions of large flow data
• An optimal error bound for \textsf{shiftedCholeskyQR3} in oblique inner product
• Limited memory gradient methods for unconstrained optimization
• Rounding error analysis of the inverse compact WY modified Gram-Schmidt algorithms
• Reorthogonalized Pythagorean variants of block classical Gram-Schmidt
• RCLUPPr: a new randomized CholeskyQR with LU preconditioning

Describes a project that uses

Uses Software

• JDQZ
• CholQR
• CholeskyQR2
• JDQR
• SparseMatrix
• mctoolbox

This page was built for publication: Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices

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