Analysis of Randomized Householder-Cholesky QR Factorization with Multisketching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912589216219136 |
|---|---|
| author | Higgins, Andrew J. Szyld, Daniel B. Boman, Erik G. Yamazaki, Ichitaro |
| author_facet | Higgins, Andrew J. Szyld, Daniel B. Boman, Erik G. Yamazaki, Ichitaro |
| contents | CholeskyQR2 and shifted CholeskyQR3 are two state-of-the-art algorithms for computing tall-and-skinny QR factorizations since they attain high performance on current computer architectures. However, to guarantee stability, for some applications, CholeskyQR2 faces a prohibitive restriction on the condition number of the underlying matrix to factorize. Shifted CholeskyQR3 is stable but has $50\%$ more computational and communication costs than CholeskyQR2. In this paper, a randomized QR algorithm called Randomized Householder-Cholesky (\texttt{rand\_cholQR}) is proposed and analyzed. Using one or two random sketch matrices, it is proved that with high probability, its orthogonality error is bounded by a constant of the order of unit roundoff for any numerically full-rank matrix, and hence it is as stable as shifted CholeskyQR3. An evaluation of the performance of \texttt{rand\_cholQR} on a NVIDIA A100 GPU demonstrates that for tall-and-skinny matrices, \texttt{rand\_cholQR} with multiple sketch matrices is nearly as fast as, or in some cases faster than, CholeskyQR2. Hence, compared to CholeskyQR2, \texttt{rand\_cholQR} is more stable with almost no extra computational or memory cost, and therefore a superior algorithm both in theory and practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_05868 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Analysis of Randomized Householder-Cholesky QR Factorization with Multisketching Higgins, Andrew J. Szyld, Daniel B. Boman, Erik G. Yamazaki, Ichitaro Numerical Analysis 65F05, 65F20, 65F25, 65G50, 15B52 CholeskyQR2 and shifted CholeskyQR3 are two state-of-the-art algorithms for computing tall-and-skinny QR factorizations since they attain high performance on current computer architectures. However, to guarantee stability, for some applications, CholeskyQR2 faces a prohibitive restriction on the condition number of the underlying matrix to factorize. Shifted CholeskyQR3 is stable but has $50\%$ more computational and communication costs than CholeskyQR2. In this paper, a randomized QR algorithm called Randomized Householder-Cholesky (\texttt{rand\_cholQR}) is proposed and analyzed. Using one or two random sketch matrices, it is proved that with high probability, its orthogonality error is bounded by a constant of the order of unit roundoff for any numerically full-rank matrix, and hence it is as stable as shifted CholeskyQR3. An evaluation of the performance of \texttt{rand\_cholQR} on a NVIDIA A100 GPU demonstrates that for tall-and-skinny matrices, \texttt{rand\_cholQR} with multiple sketch matrices is nearly as fast as, or in some cases faster than, CholeskyQR2. Hence, compared to CholeskyQR2, \texttt{rand\_cholQR} is more stable with almost no extra computational or memory cost, and therefore a superior algorithm both in theory and practice. |
| title | Analysis of Randomized Householder-Cholesky QR Factorization with Multisketching |
| topic | Numerical Analysis 65F05, 65F20, 65F25, 65G50, 15B52 |
| url | https://arxiv.org/abs/2309.05868 |