Volume 44, pp. 306-326, 2015.

Roundoff error analysis of the CholeskyQR2 algorithm

Yusaku Yamamoto, Yuji Nakatsukasa, Yuka Yanagisawa, and Takeshi Fukaya

Abstract

We consider the QR decomposition of an $m\times n$ matrix $X$ with full column rank, where $m\ge n$. Among the many algorithms available, the Cholesky QR algorithm is ideal from the viewpoint of high performance computing since it consists entirely of standard level 3 BLAS operations with large matrix sizes, and requires only one reduce and broadcast in parallel environments. Unfortunately, it is well-known that the algorithm is not numerically stable and the deviation from orthogonality of the computed $Q$ factor is of order $O(({\kappa }_2(X){)}^2\mathbf{u})$, where ${\kappa }_2(X)$ is the 2-norm condition number of $X$ and $\mathbf{u}$ is the unit roundoff. In this paper, we show that if the condition number of $X$ is not too large, we can greatly improve the stability by iterating the Cholesky QR algorithm twice. More specifically, if ${\kappa }_2(X)$ is at most $O({\mathbf{u}}^{-\frac{1}{2}})$, both the residual and deviation from orthogonality are shown to be of order $O(\mathbf{u})$. Numerical results support our theoretical analysis.

Full Text (PDF) [742 KB], BibTeX

Key words

QR decomposition, Cholesky QR, communication-avoiding algorithms, roundoff error analysis.

AMS subject classifications

15A23, 65F25, 65G50.