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

Technische Zusammenfassung: NR-SSOR-rechts-präkonditioniertes RRGMRES für nicht-bereichs-symmetrische Systeme und rangdefiziente rechte Kleinste-Quadrate-Probleme

Problemstellung
Die Generalized Minimal Residual (GMRES)-Methode ist ein Standard-Krylov-Unterraum-Iterationslöser für lineare Systeme $Ax = b$. Wenn $A$ jedoch singulär und das System inkonsistent ist (d. h. $b \notin R(A)$), ist bekannt, dass GMRES ohne die Bereitstellung einer Kleinste-Quadrate-Lösung (Least Squares, LS) zusammenbricht, sofern $A$ nicht bereichs-symmetrisch (EP) ist, was bedeutet, dass $R(A) = R(A^T)$. Insbesondere wenn $R(A^T) \neq R(A)$ – eine Bedingung, die Fälle einschließt, in denen der Index von $A$ größer als oder gleich 1 ist – existieren Anfangsvektoren $x_0$ und Rechteiten $b$, für die GMRES versagt. Darüber hinaus können die innerhalb von GMRES gelösten Kleinste-Quadrate-Teilprobleme selbst dann gefährlich schlecht konditioniert werden, wenn $b \notin R(A)$, falls $A$ bereichs-symmetrisch ist.

Bestehende Ansätze, wie etwa das ausfallsichere (breakdown-free) GMRES, bieten keine theoretischen Garantien, stets zu funktionieren. Ebenso garantieren Standardwahlen für den Präkonditionierer $B$ beim AB-GMRES-Verfahren (Anwendung von GMRES auf $ABz=b$), wie etwa $B=A^TC$ mit stationären inneren Iterationen, nicht, dass $AB$ für inkonsistente Systeme bereichs-symmetrisch ist, was potenziell zum Scheitern bei der Bestimmung einer LS-Lösung führt.

Methodik
Die Autoren schlagen eine robuste iterative Methode vor, die drei Schlüsselkomponenten kombiniert:

1. Rechts-Präkonditionierung mit $B = CA^T$: Anstatt $Ax=b$ direkt zu lösen, löst die Methode ein transformiertes Kleinste-Quadrate-Problem $\min_z \|b - ABz\|_2$, wobei $B = CA^T$ und $C \in \mathbb{R}^{n \times n}$ eine symmetrische positive definite (SPD) Matrix ist. Diese Transformation stellt sicher, dass das Produkt $AB = ACA^T$ symmetrisch und bereichs-symmetrisch ist, unabhängig davon, ob $A$ selbst bereichs-symmetrisch ist. Folglich kann die Methode eine LS-Lösung $x = CA^Tz$ ohne Abbruch bestimmen, unabhängig von einem beliebigen singulären $A$ und $b$.
2. RRGMRES (Range-Restricted GMRES): Um die mit GMRES inhärenten Konditionierungsprobleme für inkonsistente Systeme zu adressieren, verwenden die Autoren RRGMRES anstelle von Standard-GMRES. RRGMRES beschränkt den Suchraum auf den Bereich von $A$ und bietet so eine größere Stabilität für inkonsistente bereichs-symmetrische Systeme. Die theoretische Analyse zeigt, dass der kleinste Singulärwert der Hessenberg-Matrix in RRGMRES nach unten beschränkt ist, eine Eigenschaft, die in Standard-GMRES nicht garantiert werden kann.
3. NR-SSOR-Präkonditionierer: Die Arbeit führt die Verwendung der Nicht-Symmetrischen SSOR-Methode (NR-SSOR) als inneren Iterations-Rechts-Präkonditionierer zur Konstruktion der Matrix $C$ ein. Die Autoren beweisen, dass die resultierende Matrix $C$ (abgeleitet aus der NR-SSOR-Iteration) eine symmetrische positive definite (SPD) Matrix ist, sofern $A$ keine Nullspalten besitzt und der Relaxationsparameter $\omega$ die Bedingung $0 < \omega < 2$ erfüllt. Diese theoretische Garantie validiert die Verwendung von NR-SSOR innerhalb des vorgeschlagenen Rahmens sowohl für quadratische singuläre Systeme als auch für rechteckige rangdefiziente Kleinste-Quadrate-Probleme ($A \in \mathbb{R}^{m \times n}$).

Wesentliche Beiträge

• Theoretische Rechtfertigung: Das Paper beweist, dass für den NR-SSOR-Rechts-Präkonditionierer $B = CA^T$ die Matrix $C$ unter Standardbedingungen (A hat keine Nullspalten, $0 < \omega < 2$) SPD ist. Dies stellt sicher, dass $AB$ bereichs-symmetrisch ist, was es ermöglicht, robust LS-Lösungen für nicht-bereichs-symmetrische Systeme und rechteckige Probleme zu finden.
• Robustheit für inkonsistente Systeme: Es wird gezeigt, dass das vorgeschlagene NR-SSOR-rechts-präkonditionierte RRGMRES eine Kleinste-Quadrate-Lösung für ein beliebiges $b \in \mathbb{R}^m$ und ein singuläres $A$ bestimmt, einschließlich Fällen, in denen der Index von $A \ge 1$ ist und $R(A) \neq R(A^T)$.
• Erweiterung auf rechteckige Probleme: Die Methode wird erfolgreich auf unterdeterminierte und überdeterminierte rechteckige Kleinste-Quadrate-Probleme erweitert, bei denen $A$ rangdefizient sein kann.
• Vergleich mit MINRES-QLP: Die Arbeit etabliert einen Vergleichsrahmen mit MINRES-QLP, einer Methode, die für singuläre symmetrische Systeme bekannt ist, wobei angemerkt wird, dass während MINRES-QLP Min-Norm-Lösungen für konsistente Systeme findet, die vorgeschlagene Methode eine überlegene Leistung für inkonsistente Systeme bietet.

Numerische Ergebnisse
Umfangreiche numerische Experimente wurden durchgeführt auf:

1. GP inkonsistente Systeme: Matrizen mit Index 1, bei denen $R(A) \cap N(A) = \{0\}$, aber $R(A) \neq R(A^T)$.
2. Index-2 inkonsistente Systeme: Matrizen, bei denen der Index 2 ist.
3. Unterdeterminierte Kleinste-Quadrate-Probleme: Große rechteckige Matrizen (z. B. Maragal, landmarkT, lp dfl001).

Die Ergebnisse zeigen:

• Konvergenz: Standard-GMRES und RRGMRES, die direkt auf $Ax=b$ angewendet werden, scheitern oft daran, eine Kleinste-Quadrate-Lösung für diese inkonsistenten, nicht-bereichs-symmetrischen Systeme zu finden.
• Überlegenheit von NR-SSOR: Das NR-SSOR-präkonditionierte RRGMRES erreicht konsistent deutlich kleinere Residuen (oft $10^{-10}$ bis $10^{-15}$) im Vergleich zu anderen Präkonditionierern wie $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ oder $B = A^T$.
• Effizienz: Die vorgeschlagene Methode benötigt weniger Iterationen und signifikant weniger Rechenzeit (bis zu 87,9-mal schneller in spezifischen unterdeterminierten Fällen) im Vergleich zu unpräkonditionierten oder anders präkonditionierten Varianten.
• Vergleich mit MINRES-QLP: In inkonsistenten Szenarien erreichte die vorgeschlagene Methode Residuen um Größenordnungen kleiner als MINRES-QLP und erreichte diese Minima in weniger Iterationen.

Bedeutung
Das Paper behauptet, dass das vorgeschlagene NR-SSOR-rechts-präkonditionierte RRGMRES eine theoretisch gerechtfertigte und numerisch robuste Lösung für eine Klasse schwieriger linearer Algebra-Probleme bietet: singuläre, nicht-bereichs-symmetrische Systeme und rangdefiziente rechteckige Kleinste-Quadrate-Probleme. Durch den Beweis der SPD-Natur des aus NR-SSOR abgeleiteten Präkonditionierer-Matrix $C$ stellen die Autoren sicher, dass die Methode die mit Standard-GMRES verbundenen Ausfälle in inkonsistenten Settings vermeidet. Die numerischen Experimente validieren, dass dieser Ansatz nicht nur theoretisch fundiert, sondern auch praktisch effizient ist und bestehende Methoden wie AB-GMRES mit anderen Präkonditionierern sowie MINRES-QLP in Bezug auf Residuenreduktion und Rechengeschwindigkeit für inkonsistente Systeme übertrifft.