ON THE BACKWARD STABILITY OF S-STEP GMRES

Kód výsledku v IS VaVaI

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

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

ON THE BACKWARD STABILITY OF S-STEP GMRES

Popis výsledku v původním jazyce

Communication, i.e., data movement, is a critical bottleneck for the performance of classical Krylov subspace method solvers on modern computer architectures. Variants of these methods which avoid communication have been introduced, which, while equivalent in exact arithmetic, can be unstable in finite precision. In this work, we address the backward stability of s-step GMRES, also known as communication-avoiding GMRES. Building upon the &apos;&apos;modular framework&quot;&quot; proposed in [A. Buttari et al., preprint, hal-04525918v2, 2024.], we present an improved framework for simplifying the analysis of s-step GMRES, which includes standard GMRES (s = 1) as a special case, by isolating the effects of rounding errors in the QR factorization and the solution of the least squares problem. The key advantage of this new framework is that it is evident how the orthogonalization method affects the backward error, and it is not necessary to reevaluate anything other than the orthogonalization itself when modifying the orthogonalization used in GMRES. Using this framework, we analyze s-step GMRES with popular block orthogonalization methods: block modified Gram-Schmidt and reorthogonalized block classical Gram--Schmidt algorithms. An example illustrates the resulting instability of s-step GMRES when paired with the classical s-step Arnoldi process and shows the limitations of popular strategies for resolving this instability. To address this issue, we propose a modified s-step Arnoldi process that allows for much larger block size s while maintaining satisfactory accuracy, as confirmed by our numerical experiments. An example illustrates the resulting instability of s-step GMRES when paired with the classical s-step Arnoldi process and shows the limitations of popular strategies for resolving this instability. To address this issue, we propose a modified Arnoldi process that allows for much larger block size s while maintaining satisfactory accuracy, as confirmed by our numerical experiments.

Název v anglickém jazyce

ON THE BACKWARD STABILITY OF S-STEP GMRES

Popis výsledku anglicky

Communication, i.e., data movement, is a critical bottleneck for the performance of classical Krylov subspace method solvers on modern computer architectures. Variants of these methods which avoid communication have been introduced, which, while equivalent in exact arithmetic, can be unstable in finite precision. In this work, we address the backward stability of s-step GMRES, also known as communication-avoiding GMRES. Building upon the &apos;&apos;modular framework&quot;&quot; proposed in [A. Buttari et al., preprint, hal-04525918v2, 2024.], we present an improved framework for simplifying the analysis of s-step GMRES, which includes standard GMRES (s = 1) as a special case, by isolating the effects of rounding errors in the QR factorization and the solution of the least squares problem. The key advantage of this new framework is that it is evident how the orthogonalization method affects the backward error, and it is not necessary to reevaluate anything other than the orthogonalization itself when modifying the orthogonalization used in GMRES. Using this framework, we analyze s-step GMRES with popular block orthogonalization methods: block modified Gram-Schmidt and reorthogonalized block classical Gram--Schmidt algorithms. An example illustrates the resulting instability of s-step GMRES when paired with the classical s-step Arnoldi process and shows the limitations of popular strategies for resolving this instability. To address this issue, we propose a modified s-step Arnoldi process that allows for much larger block size s while maintaining satisfactory accuracy, as confirmed by our numerical experiments. An example illustrates the resulting instability of s-step GMRES when paired with the classical s-step Arnoldi process and shows the limitations of popular strategies for resolving this instability. To address this issue, we propose a modified Arnoldi process that allows for much larger block size s while maintaining satisfactory accuracy, as confirmed by our numerical experiments.

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 on Matrix Analysis and Applications

ISSN

0895-4798

e-ISSN

1095-7162

Svazek periodika

46

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

2008-2040

Kód UT WoS článku

001580457700004

EID výsledku v databázi Scopus

2-s2.0-105014621532