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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

SIAM Journal of Scientific Computing

ISSN

1064-8275

e-ISSN

1095-7197

Svazek periodika

47

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

25

Strana od-do

"A2353"-"A2377"

Kód UT WoS článku

001553344500013

EID výsledku v databázi Scopus

2-s2.0-105015746321