Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices
The Cholesky QR algorithm is an efficient communication-minimizing algorithm for computing the QR factorization of a tall-skinny matrix $X\in\mathbb{R}^{m\times n}$, where $m\gg n$. Unfortunately it is inherently unstable and often breaks down when the matrix is ill-conditioned. A recent work [Yamam...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2020
|
| _version_ | 1797102413975388160 |
|---|---|
| author | Fukaya, T Kannan, R Nakatsukasa, Y Yamamoto, Y Yanagisawa, Y |
| author_facet | Fukaya, T Kannan, R Nakatsukasa, Y Yamamoto, Y Yanagisawa, Y |
| author_sort | Fukaya, T |
| collection | OXFORD |
| description | The Cholesky QR algorithm is an efficient communication-minimizing algorithm for computing the QR factorization of a tall-skinny matrix $X\in\mathbb{R}^{m\times n}$, where $m\gg n$. Unfortunately it is inherently unstable and often breaks down when the matrix is ill-conditioned. A recent work [Yamamoto et al., ETNA, 44, pp. 306--326 (2015)] establishes that the instability can be cured by repeating the algorithm twice (called CholeskyQR$2$). However, the applicability of CholeskyQR$2$ is still limited by the requirement that the Cholesky factorization of the Gram matrix $X^{\top} X$ runs to completion, which means that it does not always work for matrices $X$ with the 2-norm condition number $\kappa_2(X)$ roughly greater than ${\bf u}^{-{1}/{2}}$, where ${\bf u}$ is the unit roundoff. In this work we extend the applicability to $\kappa_2(X)=\mathcal{O}({\bf u}^{-1})$ by introducing a shift to the computed Gram matrix so as to guarantee the Cholesky factorization $R^{\top}R= A^{\top}A+sI$ succeeds numerically. We show that the computed $AR^{-1}$ has reduced condition number that is roughly bounded by ${\bf u}^{-{1}/{2}}$, for which CholeskyQR$2$ safely computes the QR factorization, yielding a computed $Q$ of orthogonality $\|Q^{\top}Q-I\|_2$ and residual $\|A-QR\|_F/\|A\|_F$ both of the order of ${\bf u}$. Thus we obtain the required QR factorization by essentially running Cholesky QR thrice. We extensively analyze the resulting algorithm shiftedCholeskyQR3 to reveal its excellent numerical stability. The shiftedCholeskyQR3 algorithm is also highly parallelizable, and applicable and effective also when working with an oblique inner product. We illustrate our findings through experiments, in which we achieve significant speedup over alternative methods. |
| first_indexed | 2024-03-07T06:05:41Z |
| format | Journal article |
| id | oxford-uuid:edc0552b-315f-4e3b-8ff9-cb7f83bde39a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:05:41Z |
| publishDate | 2020 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:edc0552b-315f-4e3b-8ff9-cb7f83bde39a2022-03-27T11:27:32ZShifted CholeskyQR for computing the QR factorization of ill-conditioned matricesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:edc0552b-315f-4e3b-8ff9-cb7f83bde39aEnglishSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2020Fukaya, TKannan, RNakatsukasa, YYamamoto, YYanagisawa, YThe Cholesky QR algorithm is an efficient communication-minimizing algorithm for computing the QR factorization of a tall-skinny matrix $X\in\mathbb{R}^{m\times n}$, where $m\gg n$. Unfortunately it is inherently unstable and often breaks down when the matrix is ill-conditioned. A recent work [Yamamoto et al., ETNA, 44, pp. 306--326 (2015)] establishes that the instability can be cured by repeating the algorithm twice (called CholeskyQR$2$). However, the applicability of CholeskyQR$2$ is still limited by the requirement that the Cholesky factorization of the Gram matrix $X^{\top} X$ runs to completion, which means that it does not always work for matrices $X$ with the 2-norm condition number $\kappa_2(X)$ roughly greater than ${\bf u}^{-{1}/{2}}$, where ${\bf u}$ is the unit roundoff. In this work we extend the applicability to $\kappa_2(X)=\mathcal{O}({\bf u}^{-1})$ by introducing a shift to the computed Gram matrix so as to guarantee the Cholesky factorization $R^{\top}R= A^{\top}A+sI$ succeeds numerically. We show that the computed $AR^{-1}$ has reduced condition number that is roughly bounded by ${\bf u}^{-{1}/{2}}$, for which CholeskyQR$2$ safely computes the QR factorization, yielding a computed $Q$ of orthogonality $\|Q^{\top}Q-I\|_2$ and residual $\|A-QR\|_F/\|A\|_F$ both of the order of ${\bf u}$. Thus we obtain the required QR factorization by essentially running Cholesky QR thrice. We extensively analyze the resulting algorithm shiftedCholeskyQR3 to reveal its excellent numerical stability. The shiftedCholeskyQR3 algorithm is also highly parallelizable, and applicable and effective also when working with an oblique inner product. We illustrate our findings through experiments, in which we achieve significant speedup over alternative methods. |
| spellingShingle | Fukaya, T Kannan, R Nakatsukasa, Y Yamamoto, Y Yanagisawa, Y Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title | Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title_full | Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title_fullStr | Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title_full_unstemmed | Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title_short | Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices |
| title_sort | shifted choleskyqr for computing the qr factorization of ill conditioned matrices |
| work_keys_str_mv | AT fukayat shiftedcholeskyqrforcomputingtheqrfactorizationofillconditionedmatrices AT kannanr shiftedcholeskyqrforcomputingtheqrfactorizationofillconditionedmatrices AT nakatsukasay shiftedcholeskyqrforcomputingtheqrfactorizationofillconditionedmatrices AT yamamotoy shiftedcholeskyqrforcomputingtheqrfactorizationofillconditionedmatrices AT yanagisaway shiftedcholeskyqrforcomputingtheqrfactorizationofillconditionedmatrices |