Flexible GMRES converges in two phases

1. Probleemstelling

Het Flexible GMRES (FGMRES) algoritme is een standaard iteratieve solver voor lineaire systemen van grote schaal $Ax=b$ die variabele preconditionering toestaat. Deze flexibiliteit is cruciaal wanneer de preconditioner $M_j$ op zichzelf een iteratieve methode is (bijvoorbeeld in Newton-Krylov methoden) of wanneer de matrix $A$ alleen toegankelijk is via matrix-vector producten.

Ondanks de wijdverbreide toepassing blijft de convergentietheorie van FGMRES slecht begrepen, met name wat betreft hoe de residu-tolerantie ($\mu$) van de innerlijke preconditioner de convergentie van de buitenste FGMRES-lus beïnvloedt.

• Het Gat: Bestaande convergentie-afschrijvingen voor standaard GMRES vertrouwen op polynoomrepresentaties van het residu, die niet gelden voor FGMRES omdat de zoekruimte geen standaard Krylov-ruimte is vanwege de variërende preconditioners.
• De Vraag: Convergeert FGMRES geometrisch met de snelheid van de tolerantie $\mu$ van de preconditioner, of verandert het convergentiegedrag naarmate de iteraties vorderen? Kan de methode stagneren?

2. Methodologie

De auteurs ontwikkelen een rigoureuze convergentie-analyse gebaseerd op de relatie tussen FGMRES en de Flexible Full Orthogonalization Method (FFOM).

• Recursieve Afleiding van Afschrijving:

  • Zij stellen een recursieve relatie vast tussen het FGMRES-residu ($r^{FG}_m$) en het FFOM-residu ($r^{FF}_{m-1}$) gecombineerd met het preconditioner-residu ($r^P_m$).
  • Met gebruik van de eigenschap dat $r^{FG}_m \perp \text{span}(AZ_m)$, leiden zij de ongelijkheid af:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • Zij relateren de FFOM- en FGMRES-residu's via een geometrische identiteit die verband houdt met de verhouding van opeenvolgende FGMRES-residu's, wat leidt tot een recursieve afschrijving voor de contractiefactor $\gamma_m$:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{waarbij } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Expliciete Oplossing via Chebyshev-polynomen:

  • Aannemende een uniforme afschrijving voor het preconditioner-residu $\|r^P_j\| \leq \mu$, analyseren zij de recursierelatie voor de contractiefactoren.
  • Door de recursie te transformeren naar een lineair systeem, identificeren zij dat het product van contractiefactoren verband houdt met Chebyshev-polynomen van de tweede soort ($U_m$).
  • Dit stelt hen in staat een gesloten vorm a priori bovengrens af te leiden voor de residu-norm.

• Constructie van Scherpheid:

  • Om te bewijzen dat de afschrijving "scherp" is (niet kan worden verbeterd), construeren de auteurs specifieke tegenvoorbeelden. Zij tonen aan dat voor elk lineair systeem en elke $\mu \leq 1/2$, er een reeks preconditioners (en een specifieke matrix $A$) bestaat waarbij het FGMRES-residu exact gelijk is aan de afgeleide bovengrens.

3. Belangrijkste Bijdragen

A. Het Convergentiegedrag in Twee Fasen

De centrale bevinding van het paper is dat FGMRES-convergentie wordt beheerst door twee distincte fasen, afhankelijk van de tolerantie $\mu$ van de preconditioner:

1. Fase 1 (Initiële Geometrische Convergentie):

   • Voor kleine iteratieaantallen $m$ is de convergentiesnelheid ongeveer $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • Deze fase domineert wanneer $\mu$ klein is (bijvoorbeeld $\mu \ll 0.5$).

2. Fase 2 (Verslechtering of Stagnatie):

   • Naarmate $m$ toeneemt, verslechtert de convergentiesnelheid van $\mu$ naar een nieuwe asymptotische snelheid $\nu$.
   • De asymptotische snelheid wordt gegeven door:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Geval $\mu \leq 0.5$: De snelheid $\nu$ is iets groter dan $\mu$ (bijvoorbeeld als $\mu=0.1$, dan is $\nu \approx 0.1005$). Voor zeer kleine $\mu$ blijft de snelheid praktisch constant. Echter, naarmate $\mu \to 0.5$, verslechtert de snelheid aanzienlijk, waarbij deze nadert tot $\nu \approx \sqrt{\mu}$.
   • Geval $\mu > 0.5$: De methode kan stagneren of instorten na een initiële reductiefase. De "stallingsindex" $m^*$ (het aantal iteraties voor stagnatie) neemt snel af naarmate $\mu$ de 0.5 overschrijdt.

B. De Scherpe Bovengrens

De auteurs leiden de volgende scherpe bovengrens af voor het residu bij stap $m$ (aannemende $\mu \leq 1/2$):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
waarbij $U_m$ de Chebyshev-polynoom van de tweede soort is.

• Deze afschrijving is haalbaar: De auteurs bewijzen dat er lineaire systemen en reeksen preconditioners bestaan waarbij gelijkheid geldt.
• Dit impliceert dat de afgeleide afschrijving het worst-case scenario voor FGMRES onder de gegeven aannames vertegenwoordigt.

C. Voorwaarde voor Convergentiegarantie

Het paper stelt een kritieke drempel vast: FGMRES is gegarandeerd convergent naar de exacte oplossing (zonder stagnatie) dan en slechts dan als $\mu \leq 1/2$.

• Als $\mu > 1/2$, staat de theoretische afschrijving stagnatie toe, en tonen de auteurs aan dat stagnatie in de praktijk inderdaad kan optreden voor specifieke systemen.

4. Resultaten en Numerieke Demonstraties

De theoretische bevindingen worden gevalideerd door numerieke experimenten in MATLAB:

1. Verificatie van Scherpheid: Een geconstrueerd $2500 \times 2500$ systeem met een innerlijke GMRES(100) preconditioner ($\mu=0.5$) toonde aan dat het berekende FGMRES-residu exact overeenkwam met de theoretische bovengrens, wat bevestigt dat de afschrijving strak is.
2. Illustratie van Stagnatie: Voor $\mu = 0.55$ nam het residu aanvankelijk af, maar stagneerde het na 6 iteraties, wat overeenkwam met de voorspelde "stallingsindex".
3. Toepassing in de Wereld: Op een grote, schaarse matrix afkomstig van een 3D Poisson-probleem (finite element discretisatie) volgde de nieuwe afschrijving nauwkeurig het daadwerkelijke convergentiegedrag van FGMRES-GMRES, wat de praktische relevantie aantoont, zelfs voor niet-geconstrueerde systemen.

5. Betekenis en Implicaties

• Theoretische Doorbraak: Dit is het eerste werk dat een scherpe, haalbare bovengrens voor FGMRES biedt die expliciet rekening houdt met de variabele tolerantie van de preconditioner. Het lost het mysterie op waarom FGMRES soms langzamer convergeert dan verwacht, ondanks een goede innerlijke solver.
• Praktische Richtlijnen voor Afstemming:
  • Als een preconditioner kan worden afgestemd (bijvoorbeeld door een doelresidu $\mu$ in te stellen), suggereren de resultaten dat het houden van $\mu \leq 0.5$ essentieel is voor gegarandeerde convergentie.
  • Voor zeer strakke toleranties ($\mu \ll 0.5$) is het gedrag in twee fasen verwaarloosbaar, en convergeert de methode geometrisch met snelheid $\mu$.
  • Voor lossere toleranties ($\mu \approx 0.5$) moeten gebruikers een vertraging in de convergentiesnelheid verwachten naarmate het iteratieaantal groeit.
• Vergelijking met Herstart GMRES: Het paper merkt op dat hoewel herstart GMRES een theoretische convergentiesnelheid van $O(\mu^j)$ heeft, FGMRES in de praktijk vaak beter presteert door deflatie-effecten (de innerlijke solver ziet gedeflateerde rechterleden). De worst-case afschrijving voor FGMRES is echter strikt slechter dan de herstart GMRES-afschrijving wanneer $\mu$ dicht bij 0.5 ligt, wat een afweging benadrukt tussen flexibiliteit en worst-case stabiliteit.
• Beperkingen: De analyse gaat ervan uit dat $\|r^P_j\| \leq \mu$ constant is. De auteurs erkennen dat methoden zoals "fastGMRES" met gerandomiseerde schetsing een variabele $\mu$ kunnen hebben, en dat het uitbreiden van de analyse naar dergelijke gevallen een open uitdaging blijft.

Kortom, het paper biedt een definitieve karakterisering van FGMRES-convergentie, bewijst dat het in twee fasen werkt en stelt een harde limiet ($\mu \leq 0.5$) vast voor gegarandeerde convergentie, onderbouwd door scherpe wiskundige afschrijvingen en numeriek bewijs.