ePubs

The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/59135349
Record Status Checked
Record Id 59135349
Title Reorthogonalized Pythagorean variants of block classical Gram-Schmidt
Contributors
Abstract Block classical Gram-Schmidt (BCGS) is commonly used for orthogonalizing a set of vectors X in distributed computing environments due to its favorable communication properties relative to other orthogonalization approaches, such as modified Gram-Schmidt or Householder. However, it is known that BCGS (as well as recently developed low-synchronization variants of BCGS) can suffer from a significant loss of orthogonality in finite-precision arithmetic, which can contribute to instability and inaccurate solutions in downstream applications such as s-step Krylov subspace methods. A common solution to improve the orthogonality among the vectors is reorthogonalization. Focusing on the “Pythagorean” variant of BCGS, introduced in [E. Carson, K. Lund, & M. Rozložník. SIAM J. Matrix Anal. Appl. 42(3), pp. 1365–1380, 2021], which guarantees an O(ε)κ^2(X) bound on the loss of orthogonality as long as O(ε)κ^2(X) < 1, where ε denotes the unit roundoff, we introduce and analyze two reorthogonalized Pythagorean BCGS variants. These variants feature favorable communication properties, with asymptotically two synchronization points per block column, as well as an improved O(ε) bound on the loss of orthogonality. Our bounds are derived in a general fashion to additionally allow for the analysis of mixed-precision variants. We verify our theoretical results with a panel of test matrices and experiments from a new version of the BlockStab toolbox.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords Gram-Schmidt algorithm, low-synchronization, communication-avoiding, mixed precision, multiprecision, loss of orthogonality, stability
Funding Information EU, ERC (101075632); Charles University, GAUK (202722); U.S. Department of Energy Office of Science and the National Nuclear Security Administration, Exascale Computing Project (17-SC-20-SC); Charles University Research Centre, UNCE (24/SCI/005)
Related Research Object(s): 10.48550/arXiv.2405.01298
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Preprint SIAM J Matrix Anal A 2024. https://arxiv.org/pdf/2405.01298v3 2024