A stable one-synchronization variant of reorthogonalized block classical Gram--Schmidt
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918045809639424 |
|---|---|
| author | Carson, Erin Ma, Yuxin |
| author_facet | Carson, Erin Ma, Yuxin |
| contents | The block classical Gram--Schmidt (BCGS) algorithm and its reorthogonalized variant are widely-used methods for computing the economic QR factorization of block columns $X$ due to their lower communication cost compared to other approaches such as modified Gram--Schmidt and Householder QR. To further reduce communication, i.e., synchronization, there has been a long ongoing search for a variant of reorthogonalized BCGS variant that achieves $O(u)$ loss of orthogonality while requiring only \emph{one} synchronization point per block column, where $u$ represents the unit roundoff. Utilizing Pythagorean inner products and delayed normalization techniques, we propose the first provably stable one-synchronization reorthogonalized BCGS variant, demonstrating that it has $O(u)$ loss of orthogonality under the condition $O(u) κ^2(X) \leq 1/2$, where $κ(\cdot)$ represents the condition number.
By incorporating one additional synchronization point, we develop a two-synchronization reorthogonalized BCGS variant which maintains $O(u)$ loss of orthogonality under the improved condition $O(u) κ(X) \leq 1/2$. An adaptive strategy is then proposed to combine these two variants, ensuring $O(u)$ loss of orthogonality while using as few synchronization points as possible under the less restrictive condition $O(u) κ(X) \leq 1/2$. As an example of where this adaptive approach is beneficial, we show that using the adaptive orthogonalization variant, $s$-step GMRES achieves a backward error comparable to $s$-step GMRES with BCGSI+, also known as BCGS2, both theoretically and numerically, but requires fewer synchronization points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07077 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A stable one-synchronization variant of reorthogonalized block classical Gram--Schmidt Carson, Erin Ma, Yuxin Numerical Analysis 65F10, 65F25, 65G50, 65Y20 The block classical Gram--Schmidt (BCGS) algorithm and its reorthogonalized variant are widely-used methods for computing the economic QR factorization of block columns $X$ due to their lower communication cost compared to other approaches such as modified Gram--Schmidt and Householder QR. To further reduce communication, i.e., synchronization, there has been a long ongoing search for a variant of reorthogonalized BCGS variant that achieves $O(u)$ loss of orthogonality while requiring only \emph{one} synchronization point per block column, where $u$ represents the unit roundoff. Utilizing Pythagorean inner products and delayed normalization techniques, we propose the first provably stable one-synchronization reorthogonalized BCGS variant, demonstrating that it has $O(u)$ loss of orthogonality under the condition $O(u) κ^2(X) \leq 1/2$, where $κ(\cdot)$ represents the condition number. By incorporating one additional synchronization point, we develop a two-synchronization reorthogonalized BCGS variant which maintains $O(u)$ loss of orthogonality under the improved condition $O(u) κ(X) \leq 1/2$. An adaptive strategy is then proposed to combine these two variants, ensuring $O(u)$ loss of orthogonality while using as few synchronization points as possible under the less restrictive condition $O(u) κ(X) \leq 1/2$. As an example of where this adaptive approach is beneficial, we show that using the adaptive orthogonalization variant, $s$-step GMRES achieves a backward error comparable to $s$-step GMRES with BCGSI+, also known as BCGS2, both theoretically and numerically, but requires fewer synchronization points. |
| title | A stable one-synchronization variant of reorthogonalized block classical Gram--Schmidt |
| topic | Numerical Analysis 65F10, 65F25, 65G50, 65Y20 |
| url | https://arxiv.org/abs/2411.07077 |