Geodesic
Roundoff error analysis of the CholeskyQR2 algorithm
Electronic transactions on numerical analysis, Tome 44 (2015), pp. 306-326.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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},
     publisher = {mathdoc},
     volume = {44},
     year = {2015},
     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
PB  - mathdoc
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
%I mathdoc
%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/