Geodesic
Roundoff error analysis of the CholeskyQR2 algorithm
Electronic transactions on numerical analysis, Tome 44 (2015), pp. 306-326
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{\bf u})$, where $\kappa_2(X)$ is the 2-norm condition number of $X$ and ${\bf 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({\bf u}^{-\frac{1}{2}})$, both the residual and deviation from orthogonality are shown to be of order $O({\bf u})$. Numerical results support our theoretical analysis.
Classification : 15A23, 65F25, 65G50
Keywords: QR decomposition, Cholesky QR, communication-avoiding algorithms, roundoff error analysis 
@article{ETNA_2015__44__a14,
     author = {Yamamoto,  Yusaku and Nakatsukasa,  Yuji and Yanagisawa,  Yuka and Fukaya,  Takeshi},
     title = {Roundoff error analysis of the {CholeskyQR2} algorithm},
     journal = {Electronic transactions on numerical analysis},
     pages = {306--326},
     year = {2015},
     volume = {44},
     zbl = {1330.65049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2015__44__a14/}
}
TY  - JOUR
AU  - Yamamoto,  Yusaku
AU  - Nakatsukasa,  Yuji
AU  - Yanagisawa,  Yuka
AU  - Fukaya,  Takeshi
TI  - Roundoff error analysis of the CholeskyQR2 algorithm
JO  - Electronic transactions on numerical analysis
PY  - 2015
SP  - 306
EP  - 326
VL  - 44
UR  - http://geodesic.mathdoc.fr/item/ETNA_2015__44__a14/
LA  - en
ID  - ETNA_2015__44__a14
ER  - 
%0 Journal Article
%A Yamamoto,  Yusaku
%A Nakatsukasa,  Yuji
%A Yanagisawa,  Yuka
%A Fukaya,  Takeshi
%T Roundoff error analysis of the CholeskyQR2 algorithm
%J Electronic transactions on numerical analysis
%D 2015
%P 306-326
%V 44
%U http://geodesic.mathdoc.fr/item/ETNA_2015__44__a14/
%G en
%F ETNA_2015__44__a14
Yamamoto,  Yusaku; Nakatsukasa,  Yuji; Yanagisawa,  Yuka; Fukaya,  Takeshi. Roundoff error analysis of the CholeskyQR2 algorithm. Electronic transactions on numerical analysis, Tome 44 (2015), pp. 306-326. http://geodesic.mathdoc.fr/item/ETNA_2015__44__a14/