A STABLE ONE-SYNCHRONIZATION VARIANT OF REORTHOGONALIZED BLOCK CLASSICAL GRAM--SCHMIDT

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509862" target="_blank" >RIV/00216208:11320/25:10509862 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Ta~Meyx71I" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Ta~Meyx71I</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/24M1709017" target="_blank" >10.1137/24M1709017</a>

Result language

angličtina

Original language name

A STABLE ONE-SYNCHRONIZATION VARIANT OF REORTHOGONALIZED BLOCK CLASSICAL GRAM--SCHMIDT

Original language description

The block classical Gram--Schmidt (BCGS) algorithm and its reorthogonalized variant are widely used methods for computing the thin QR factorization of a given matrix bfscrX with block vectors 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 that achieves O(u) loss of orthogonality while requiring only 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)k2(bfscrX) leq 1/2, where k(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)k(bfscrX) 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)k(bfscrX) 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

SIAM Journal of Scientific Computing

ISSN

1064-8275

e-ISSN

1095-7197

Volume of the periodical

47

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

25

Pages from-to

"A2353"-"A2377"

UT code for WoS article

001553344500013

EID of the result in the Scopus database

2-s2.0-105015746321