Iterated Gauss-Seidel GMRES

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F24%3A00585518" target="_blank" >RIV/67985840:_____/24:00585518 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/24:10493576

Výsledek na webu

<a href="https://doi.org/10.1137/22M1491241" target="_blank" >https://doi.org/10.1137/22M1491241</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Iterated Gauss-Seidel GMRES

Popis výsledku v původním jazyce

The GMRES algorithm of Saad and Schultz [SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856--869] is an iterative method for approximately solving linear systems Ax = b, with initial guess x0 and residual r0 = b- Ax0. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of Vk). It is well known that this process can be viewed as a QR factorization of the matrix Bk = [r0,AVk ] at each iteration. Despite an O(varepsilon)kappa(Bk) loss of orthogonality, for unit roundoff varepsilon and condition number kappa , the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. [SIAM J. Matrix Anal. Appl., 28 (2006), pp. 264--284]. We present an iterated Gauss--Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe [Linear Algebra Appl., 52 (1983), pp. 591--601] and S'wirydowicz et al. [Numer. Linear Algebra Appl., 28 (2020), pp. 1--20]. IGS-GMRES maintains orthogonality to the level O(varepsilon)kappa(Bk) or O(varepsilon), depending on the choice of one or two iterations, for two Gauss--Seidel iterations, the computed Krylov basis vectors remain orthogonal to working accuracy and the smallest singular value of Vk remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly nonnormal systems.

Název v anglickém jazyce

Iterated Gauss-Seidel GMRES

Popis výsledku anglicky

The GMRES algorithm of Saad and Schultz [SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856--869] is an iterative method for approximately solving linear systems Ax = b, with initial guess x0 and residual r0 = b- Ax0. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of Vk). It is well known that this process can be viewed as a QR factorization of the matrix Bk = [r0,AVk ] at each iteration. Despite an O(varepsilon)kappa(Bk) loss of orthogonality, for unit roundoff varepsilon and condition number kappa , the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. [SIAM J. Matrix Anal. Appl., 28 (2006), pp. 264--284]. We present an iterated Gauss--Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe [Linear Algebra Appl., 52 (1983), pp. 591--601] and S'wirydowicz et al. [Numer. Linear Algebra Appl., 28 (2020), pp. 1--20]. IGS-GMRES maintains orthogonality to the level O(varepsilon)kappa(Bk) or O(varepsilon), depending on the choice of one or two iterations, for two Gauss--Seidel iterations, the computed Krylov basis vectors remain orthogonal to working accuracy and the smallest singular value of Vk remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly nonnormal systems.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA23-06159S" target="_blank" >GA23-06159S: Vírové struktury: pokročilé metody identifikace a efektivní numerické simulace</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

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

ISSN

1064-8275

e-ISSN

1095-7197

Svazek periodika

46

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

26

Strana od-do

"S254"-"S279"

Kód UT WoS článku

001308408900002

EID výsledku v databázi Scopus

2-s2.0-85192678897