How to make Simpler GMRES and GCR more Stable

0310698 - ÚI 2010 RIV US eng J - Journal Article
Jiránek, P. - Rozložník, Miroslav - Gutknecht, M. H.
How to make Simpler GMRES and GCR more Stable.
[Jak stabilizovat metody Simpler GMRES and GCR?]
SIAM Journal on Matrix Analysis and Applications. Roč. 30, č. 4 (2008), s. 1483-1499. ISSN 0895-4798. E-ISSN 1095-7162
R&D Projects: GA MŠMT 1M0554; GA AV ČR IAA100300802; GA AV ČR IAA1030405
Institutional research plan: CEZ:AV0Z10300504
Keywords : large-scale nonsymmetric linear systems * Krylov subspace methods * minimum residual methods * numerical stability * rounding errors
Subject RIV: BA - General Mathematics
Impact factor: 1.328, year: 2008

In this paper we analyze the numerical behavior of several minimum residual methods, which are mathematically equivalent to the GMRES method. Two main approaches are compared: the one that computes the approximate solution in terms of a Krylov space basis from an upper triangular linear system for the coordinates, and the one where the approximate solutions are updated with a simple recursion formula. We show that a different choice of the basis can significantly influence the numerical behavior of the resulting implementation. While Simpler GMRES and ORTHODIR are less stable due to the ill-conditioning of the basis used, the residual basis is well-conditioned as long as we have a reasonable residual norm decrease. These results lead to a new implementation, which is conditionally backward stable, and they explain the experimentally observed fact that the GCR method delivers very accurate approximate solutions when it converges fast enough without stagnation.

V této práci analyzujeme numerické chování několika metod minimalizujících normu rezidua, které jsou matematicky ekvivalentní metodě GMRES. Porovnáváme dva základní postupy: postup, který je založen na výpočtu aproximace řešení z horní trojúhelníkové soustavy pro její souřadnice a postup, kde jsou aproximace postupně upravovány jednoduchou rekurzní formulí. Práce ukazuje, že volba báze vypočteného prostoru může podstatným způsoben ovlivnit numerickou stabilitu implementace daných metod. Z důvodu špatné podmíněnosti zvolené báze jsou implementace Simpler GMRES a ORTHODIR méně stabilní. Na druhé straně se ukazuje, ze pokud metoda konverguje dostatečně rychle, je báze reziduí dobře podmíněná. Tyto výsledky pak vedou k nove implementaci, která je podmíněně zpětně stabilní, a potvrzují experimentálně známý fakt, že metoda GCR v případě dostatečně rychlé konvergence generuje velice přesné aproximace řešení.
Permanent Link: http://hdl.handle.net/11104/0162481