An improved shifted CholeskyQR based on columns

Abstract

Among all the deterministic CholeskyQR-type algorithms, Shifted CholeskyQR3 is specifically designed to address the QR factorization of ill-conditioned matrices. This algorithm introduces a shift parameter s to prevent failure during the initial Cholesky factorization step, making the choice of this parameter critical for the algorithm’s effectiveness. Our goal is to identify a smaller s compared to the traditional selection based on ‖X‖2. In this research, we propose a new matrix norm called the g-norm, which is based on the column properties of X. This norm allows us to obtain a reduced shift parameter s for the Shifted CholeskyQR3 algorithm, thereby improving the sufficient condition of κ2(X) for this method. We provide rigorous proofs of orthogonality and residuals for the improved algorithm using our proposed s. Numerical experiments confirm the enhanced numerical stability of orthogonality and residuals with the reduced s. We find that Shifted CholeskyQR3 can effectively handle ill-conditioned X with a larger κ2(X) when using our reduced s compared to the original s. Furthermore, we compare CPU times with other algorithms to assess performance improvements.