NR-SSOR right preconditioned RRGMRES for arbitrary singular systems and least squares problems

Technische Samenvatting: NR-SSOR Recht Geconditioneerde RRGMRES voor Niet-Bereik-Symmetrische Systemen en Rang-Deficiënte Rectangulaire Kleinste Kwadraten Problemen

Probleemstelling
De Generalized Minimal Residual (GMRES) methode is een standaard Krylov-subruimte iteratieve solver voor lineaire systemen $Ax = b$. Echter, wanneer $A$ singulier is en het systeem inconsistent is (d.w.z. $b \notin R(A)$), staat GMRES erom bekend dat het vastloopt zonder een kleinste kwadraten (LS) oplossing te leveren, tenzij $A$ bereik-symmetrisch (EP) is, wat betekent dat $R(A) = R(A^T)$. Specifiek, als $R(A^T) \neq R(A)$—een conditie die gevallen omvat waarin de index van $A$ groter dan of gelijk aan 1 is—bestaan er initiële vectoren $x_0$ en rechterzijden $b$ waarvoor GMRES faalt. Bovendien, zelfs wanneer $A$ bereik-symmetrisch is, kunnen de kleinste kwadraten subproblemen die binnen GMRES worden opgelost, gevaarlijk slecht geconditioneerd raken als $b \notin R(A)$.

Bestaande benaderingen, zoals breakdown-vrije GMRES, missen theoretische garanties om altijd te werken. Ook al biedt de AB-GMRES methode (het toepassen van GMRES op $ABz=b$) een manier om met singuliere systemen om te gaan, standaard keuzes voor de preconditioner $B$ (zoals $B=A^TC$ met stationaire innerlijke iteraties) garanderen niet dat $AB$ bereik-symmetrisch is voor inconsistente systemen, wat potentieel kan leiden tot het falen bij het vinden van een LS oplossing.

Methodologie
De auteurs stellen een robuuste iteratieve methode voor die drie kerncomponenten combineert:

1. Recht Preconditionering met $B = CA^T$: In plaats van $Ax=b$ direct op te lossen, lost de methode een getransformeerd kleinste kwadraten probleem op: $\min_z \|b - ABz\|_2$ waarbij $B = CA^T$ en $C \in \mathbb{R}^{n \times n}$ een symmetrische positief definiete (SPD) matrix is. Deze transformatie zorgt ervoor dat het product $AB = ACA^T$ symmetrisch en bereik-symmetrisch is, ongeacht of $A$ zelf bereik-symmetrisch is. Bij consequentie kan de methode een LS oplossing $x = CA^Tz$ bepalen zonder breakdown voor een willekeurige singuliere $A$ en $b$.
2. RRGMRES (Range-Restricted GMRES): Om de ill-conditioning problemen aan te pakken die inherent zijn aan GMRES voor inconsistente systemen, gebruiken de auteurs RRGMRES in plaats van standaard GMRES. RRGMRES beperkt de zoekruimte tot het bereik van $A$, wat zorgt voor grotere stabiliteit voor inconsistente bereik-symmetrische systemen. Theoretische analyse toont aan dat de kleinste singuliere waarde van de Hessenberg-matrix in RRGMRES onderaan begrensd is, een eigenschap die in standaard GMRES niet gegarandeerd is.
3. NR-SSOR Preconditioner: Het artikel introduceert het gebruik van de Non-Symmetric SSOR (NR-SSOR) methode als een innerlijke iteratie recht preconditioner om de matrix $C$ te construeren. De auteurs bewijzen dat als $A$ geen nul-kolommen heeft en de relaxatieparameter $\omega$ voldoet aan $0 < \omega < 2$, de resulterende matrix $C$ (afgeleid van de NR-SSOR iteratie) een symmetrische positief definitie (SPD) matrix is. Deze theoretische garantie valideert het gebruik van NR-SSOR binnen het voorgestelde kader voor zowel vierkante singuliere systemen als rectangulaire rang-deficiënte kleinste kwadraten problemen ($A \in \mathbb{R}^{m \times n}$).

Belangrijkste Bijdragen

• Theoretische Rechtvaardiging: Het paper bewijst dat voor de NR-SSOR recht preconditioner $B = CA^T$, de matrix $C$ SPD is onder standaard condities ($A$ heeft geen nul-kolommen, $0 < \omega < 2$). Dit zorgt ervoor dat $AB$ bereik-symmetrisch is, waardoor de methode robuust LS oplossingen kan vinden voor niet-bereik-symmetrische systemen en rectangulaire problemen.
• Robuustheid voor Inconsistente Systemen: De voorgestelde NR-SSOR recht geconditioneerde RRGMRES is aangetoond een kleinste kwadraten oplossing te bepalen voor een willekeurige $b \in \mathbb{R}^m$ en singuliere $A$, inclusief gevallen waar de index van $A \ge 1$ en $R(A) \neq R(A^T)$.
• Extensie naar Rectangulaire Problemen: De methode wordt succesvol uitgebreid naar ondergedetermineerde en overgedetermineerde rectangulaire kleinste kwadraten problemen, waarbij $A$ rang-deficiënt kan zijn.
• Vergelijking met MINRES-QLP: Het paper stelt een vergelijkingskader vast met MINRES-QLP, een methode die bekend staat om het afhandelen van singuliere symmetrische systemen, waarbij wordt opgemerkt dat terwijl MINRES-QLP min-norm oplossingen vindt voor consistente systemen, de voorgestelde methode superieure prestaties biedt voor inconsistente systemen met niet-bereik-symmetrische matrices.

Numerieke Resultaten
Uitgebreide numerieke experimenten werden uitgevoerd op:

1. GP Inconsistente Systemen: Matrices met index 1 waarbij $R(A) \cap N(A) = \{0\}$ maar $R(A) \neq R(A^T)$.
2. Index 2 Inconsistente Systemen: Matrices waarbij de index 2 is.
3. Ondergedetermineerde Kleinste Kwadraten Problemen: Grote rectangulaire matrices (bijv. Maragal, landmarkT, lp dfl001).

De resultaten tonen aan dat:

• Convergentie: Standaard GMRES en RRGMRES toegepast direct op $Ax=b$ falen vaak in het convergeren naar een kleinste kwadraten oplossing voor deze inconsistente, niet-bereik-symmetrische systemen.
• Superioriteit van NR-SSOR: De NR-SSOR geconditioneerde RRGMRES bereikt consistent aanzienlijk kleinere residuen (vaak $10^{-10}$ tot $10^{-15}$) vergeleken met andere preconditioners zoals $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ of $B = A^T$.
• Efficiëntie: De voorgestelde methode vereist minder iteraties en aanzienlijk minder rekentijd (tot 87,9 keer sneller in specifieke ondergedetermineerde gevallen) vergeleken met ongeconditioneerde of anders geconditioneerde varianten.
• Vergelijking met MINRES-QLP: In inconsistente scenario's bereikte de voorgestelde methode residuen die orden van grootte kleiner waren dan MINRES-QLP en bereikte deze minima in minder iteraties.

Betekenis
Het paper claimt dat de voorgestelde NR-SSOR recht geconditioneerde RRGMRES een theoretisch gerechtvaardigde en numeriek robuuste oplossing biedt voor een klasse van moeilijke lineaire algebra problemen: singuliere, niet-bereik-symmetrische systemen en rang-deficiënte rectangulaire kleinste kwadraten problemen. Door de SPD-aard van de preconditioner matrix $C$ afgeleid van NR-SSOR te bewijzen, zorgt de auteur ervoor dat de methode de breakdowns vermijdt die geassocieerd worden met standaard GMRES in inconsistente settings. De numerieke experimenten valideren dat deze benadering niet alleen theoretisch solide is, maar ook praktisch efficiënt, waarbij het bestaande methoden zoals AB-GMRES met andere preconditioners en MINRES-QLP overtreft in termen van residu-reductie en computationele snelheid voor inconsistente systemen.