Stabilizing randomized GMRES through flexible GMRES

Technische Samenvatting: Stabilisatie van Geraandomiseerde GMRES via Flexible GMRES

Probleemstelling
Het artikel behandelt de uitdaging om grote, schaarse lineaire systemen $Ax = b$ op te lossen met behulp van geraandomiseerde Krylov-onderruimte-methoden. Hoewel randomisatie zich als zeer effectief heeft bewezen voor benadering van matrices met lage rang en voor overdetermined kleinste-kwadratenproblemen, is de toepassing ervan op algemene niet-symmetrische lineaire systemen moeilijker. In tegenstelling tot overdetermined systemen ontbreekt bij algemene lineaire systemen de inherente redundantie, waardoor de oplossingsvector gevoelig is voor verstoringen in alle matrixcomponenten. Bijgevolg is "het probleem schetsen" minder levensvatbaar dan "het algoritme schetsen".

Bestaande geraandomiseerde Krylov-oplossers, zoals geschetste GMRES (sGMRES), beogen de dure orthogonalisatiekosten die gepaard gaan met standaard GMRES te verminderen door het probleem te projecteren naar een lager-dimensionale ruimte met behulp van een schetsoperator $S$. sGMRES lijdt echter aan stabiliteitsproblemen. Specifiek kan bij het gebruik van afgeknipte Arnoldi-processen om niet-orthogonale Krylov-bases te genereren, de basis sterk slecht geconditioneerd worden, wat leidt tot stagnatie of numerieke instabiliteit. Hoewel het herstarten van sGMRES een veelgebruikt middel is, faalt dit vaak bij het convergeren voor moeilijke problemen, aangezien de voor convergentie vereiste herstartlengte onaanvaardbaar groot kan zijn.

Methodologie
De auteurs stellen een hybride aanpak voor die Flexible GMRES (FGMRES) gebruikt als een buitenste wrapper om geschetste GMRES (sGMRES) te stabiliseren. De kernmethodologie omvat de volgende componenten:

1. Theoretische Grondslag (Foutgrens voor FGMRES-residu):
   De auteurs leiden een nieuwe, praktische bovengrens af voor het FGMRES-residu. Door een flexibele versie van de Full Orthogonalization Method (FFOM) in te voeren, stellen zij vast dat het FGMRES-residu bij iteratie $m$, genoteerd als $\|r_m\|$, begrensd is door het product van het FFOM-residu bij de vorige iteratie en het residu van de binnenste preconditioner:
   $$\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$$
   Deze grens impliceert dat, indien de binnenste solver (de preconditioner) het residu effectief vermindert, de buitenste FGMRES-iteratie ook het globale residu zal verminderen, mits de FGMRES- en FFOM-residuen vergelijkbaar blijven. Dit theoretische resultaat rechtvaardigt het gebruik van FGMRES om niet-stijgende residunormen te garanderen, zelfs als de binnenste solver instabiel is.

2. Algoritmische Structuur (FGMRES-sGMRES):
   Het voorgestelde algoritme, aangeduid als fastGMRES, werkt als volgt:

   • Buitenste Lus: Voert FGMRES-iteraties uit.
   • Binnenste Lus (Preconditioner): Bij elke buitenste iteratie $j$ is de preconditioner $M_j$ een benaderende oplossing voor $Az = v_j$, berekend via $k$ iteraties van sGMRES.
   • sGMRES-implementatie: De binnenste sGMRES-solver construeert een Krylov-basis $B_k$ met behulp van een afgeknipt Arnoldi-proces (alleen orthogonaliseren tegen de laatste $t$ vectoren). De oplossing $z_j$ wordt gevonden door het geschetste residu $\|S(v_j - Az)\|$ te minimaliseren over het bereik van $B_k$.
   • Stopcriteria: De binnenste sGMRES-lus wordt beëindigd op basis van drie voorwaarden:
     1. Een maximum iteratielimiet $k_{\max}$ (bijv. 500) om het geheugen te beheersen.
     2. Een drempelwaarde voor het conditiongetal van de geschetste basis $SAB_k$ (bijv. $10^{15}$) om ernstige slechte conditionering te voorkomen.
     3. De geschatte FGMRES-residugrens die onder de doeltolerantie daalt.

3. Parametrisatie:
   De methode vereist minimale parameterafstelling. De primaire parameter is de Arnoldi-afknipparameter $t$. De auteurs onderzoeken $t=0$ (een pure machtsbasis zonder orthogonalisatie) tot $t=5$.

Belangrijkste Bijdragen

• Stabilisatiemechanisme: Het artikel demonstreert dat het inpakken van sGMRES binnen een buitenste FGMRES-lus de geraandomiseerde solver effectief stabiliseert. De buitenste lus zorgt voor niet-stijgende residunormen, waarmee de stagnatieproblemen die typerend zijn voor herstartte sGMRES worden overwonnen.
• Nieuwe Residugrens: De afleiding van de grens $\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$ biedt een theoretische rechtvaardiging voor de robuustheid van de methode en vormt een praktisch hulpmiddel om convergentie te voorspellen op basis van de prestaties van de binnenste solver.
• Eenvoud en Robuustheid: De voorgestelde "fastGMRES"-methode vereist zeer weinig gebruikersinvoer. In tegenstelling tot andere gedeflateerde herstartmethoden (zoals GMRES-SDR of RGS-GMRES-MDR) die zorgvuldige selectie van onderruimtegroottes en het aantal gedeflateerde vectoren vereisen, presteert fastGMRES robuust met vaste parameters ($t=0$ of kleine $t$, vaste schetsdimensie).
• Efficiëntie via $t=0$: De auteurs rapporteren een tegenintuïtieve bevinding dat het instellen van de afknipparameter $t=0$ (geen orthogonalisatie in de binnenste lus) vaak de beste prestaties in tijd tot oplossing oplevert, met name voor problemen waarvoor matrix-vectorproducten goedkoop zijn.

Numerieke Resultaten
De auteurs evalueren de methode op verschillende uitdagende problemen uit de SuiteSparse Matrix Collection en andere benchmarks:

• vas stokes 1M: Een moeilijk probleem waarbij herstartte sGMRES stagneert. De door FGMRES gestabiliseerde versie convergeert gestaag. De methode presteert aanzienlijk beter dan herstartte sGMRES en is concurrerend met GMRES-SDR en RGS-GMRES-MDR, ondanks dat minder parameterkeuzes nodig zijn.
• NACA12: De methode convergeert robuust met en zonder ILU-preconditioning. Opmerkelijk is dat $t=0$ de snelste configuratie blijft, zelfs voor het niet-gepreconditioneerde geval waarbij andere methoden worstelen of time-outen.
• ML Geer: Een grootschalig probleem ($n \approx 1,5$ miljoen). De methode convergeert robuust voor alle geteste $t$, hoewel $t=0$ een lichte vertraging vertoont in latere iteraties als gevolg van de toenemende kosten van de buitenste FGMRES-orthogonalisatie.
• Benchmarking: In een vergelijking met BiCGSTAB, GMRES, GMRES-DR en GMRES-SDR over 10 problemen behoort fastGMRES tot de meest betrouwbare. Het faalt slechts bij één probleem om binnen de tijdslimiet te convergeren (waarbij ook alle andere methoden faalden), terwijl BiCGSTAB bij twee problemen faalt. Hoewel GMRES-SDR met zorgvuldig afgestemde parameters soms sneller is, bereikt fastGMRES vergelijkbare prestaties zonder de noodzaak van parameterafstelling.

Betekenis en Beweringen
Het artikel beweert dat de combinatie van FGMRES en sGMRES een "praktische geraandomiseerde solver" biedt die efficiëntie, robuustheid en gebruiksgemak in evenwicht brengt. De betekenis ligt in:

1. Betrouwbaarheid: Het garandeert niet-stijgende residunormen, een eigenschap die vaak verloren gaat bij geraandomiseerde of herstartte Krylov-methoden.
2. Lage Afstelflat: Het elimineert de noodzaak voor complexe parameterselectie (zoals aantallen deflatie of herstartlengtes) die andere geavanceerde Krylov-methoden teisteren.
3. Berekenings-efficiëntie: De verrassende effectiviteit van $t=0$ suggereert dat het vermijden van inproducten in de binnenste lus zeer voordelig kan zijn, met name voor parallelle computing en scenario's met gemengde precisie waar communicatie voor orthogonalisatie een knelpunt vormt.

De auteurs concluderen dat, hoewel de methode niet altijd de best-geoptimaliseerde bestaande oplossers overtreft, het een zeer concurrerend, "zet-en-vergeet"-alternatief biedt dat robuust is voor een breed scala aan moeilijke lineaire systemen. Voor toekomstig werk wordt voorgesteld om multi-level FGMRES-structuren te onderzoeken om de orthogonalisatiekosten van de buitenste lus voor zeer grote iteratieaantallen te mitigeren.