LU-Cholesky QR algorithms for thin QR decomposition

摘要

This paper aims to propose the LU-Cholesky QR algorithms for thin QR decomposition (also called economy size or reduced QR decomposition). CholeskyQR is known as a fast algorithm employed for thin QR decomposition, and CholeskyQR2 aims to improve the orthogonality of a Q-factor computed by CholeskyQR. Although such Cholesky QR algorithms can efficiently be implemented in high-performance computing environments, they are not applicable for ill-conditioned matrices, as compared to the Householder QR and the Gram-Schmidt algorithms. To address this problem, we apply the concept of LU decomposition to the Cholesky QR algorithms, i.e., the idea is to use LU-factors of a given matrix as preconditioning before applying Cholesky decomposition. Moreover, we present rounding error analysis of the proposed algorithms on the orthogonality and residual of computed QR-factors. Numerical examples provided in this paper illustrate the efficiency of the proposed algorithms in parallel computing on both shared and distributed memory computers. (C) 2019 Elsevier B.V. All rights reserved.