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

Sintesi Tecnica: NR-SSOR Right Preconditioned RRGMRES per Sistemi Non-Range-Symmetric e Problemi di Minimi Quadrati Rettangolari a Rango Deficiente

Enunciato del Problema
Il metodo Generalized Minimal Residual (GMRES) è un tipico risolutore iterativo di sottospazio di Krylov per sistemi lineari $Ax = b$. Tuttavia, quando $A$ è singolare e il sistema è incoerente (ovvero $b \notin R(A)$), si sa che GMRES può fallire senza fornire una soluzione di minimi quadrati (LS) a meno che $A$ non sia range-simmetrica (EP), ovvero $R(A) = R(A^T)$. Nello specifico, se $R(A^T) \neq R(A)$—una condizione che include i casi in cui l'indice di $A$ è maggiore o uguale a 1—esistono vettori iniziali $x_0$ e termini noti $b$ per i quali GMRES fallisce. Inoltre, anche quando $A$ è range-simmetrica, i sottoproblemi di minimi quadrati risolti all'interno di GMRES possono diventare pericolosamente mal condizionati se $b \notin R(A)$.

Gli approcci esistenti, come il GMRES privo di breakdown, mancano di garanzie teoriche di funzionamento costante. Allo stesso modo, sebbene il metodo AB-GMRES (che applica GMRES a $ABz=b$) possa gestire sistemi singolari, le scelte standard per il precondizionatore $B$ (come $B=A^TC$ con iterazioni interne stazionarie) non garantiscono che $AB$ sia range-simmetrico per sistemi incoerenti, il che può portare al fallimento nel trovare una soluzione LS.

Metodologia
Gli autori propongono un metodo iterativo robusto che combina tre componenti chiave:

1. Precondizionamento a Destra con $B = CA^T$: Invece di risolvere direttamente $Ax=b$, il metodo risolve un problema di minimi quadrati trasformato $\min_z \|b - ABz\|_2$ dove $B = CA^T$ e $C \in \mathbb{R}^{n \times n}$ è una matrice simmetrica definita positiva (SPD). Questa trasformazione assicura che il prodotto $AB = ACA^T$ sia simmetrico e range-simmetrico, indipendentemente dal fatto che $A$ stessa sia range-simmetrica. Di conseguenza, il metodo può determinare una soluzione LS $x = CA^Tz$ senza breakdown per arbitrarie matrici singolari $A$ e $b$.
2. RRGMRES (Range-Restricted GMRES): Per affrontare i problemi di mal condizionamento inerenti a GMRES per sistemi incoerenti, gli autori impiegano RRGMRES invece del GMRES standard. RRGMRES restringe lo spazio di ricerca all'interno del range di $A$, fornendo una maggiore stabilità per sistemi range-simmetrici incoerenti. L'analisi teorica mostra che il valore singolare minimo della matrice di Hessenberg in RRGMRES è limitato inferiormente, una proprietà non garantita in GMRES standard.
3. Precondizionatore NR-SSOR: Il documento introduce l'uso del metodo Non-Symmetric SSOR (NR-SSOR) come precondizionatore a destra tramite iterazioni interne per costruire la matrice $C$. Gli autori dimostrano che se $A$ non ha colonne nulle e il parametro di rilassamento $\omega$ soddisfa $0 < \omega < 2$, la matrice $C$ risultante (derivata dall'iterazione NR-SSOR) è una matrice simmetrica definita positiva. Questa garanzia teorica valida l'uso di NR-SSOR all'interno del framework proposto sia per sistemi quadrati singolari che per problemi di minimi quadrati rettangolari a rango deficiente ($A \in \mathbb{R}^{m \times n}$).

Contributi Chiave

• Giustificazione Teorica: Il documento prova che per il precondizionatore a destra NR-SSOR $B = CA^T$, la matrice $C$ è SPD sotto condizioni standard (A non ha colonne nulle, $0 < \omega < 2$). Ciò assicura che $AB$ sia range-simmetrica, permettendo al metodo di trovare robustamente soluzioni LS per sistemi non-range-simmetrici e problemi rettangolari.
• Robustezza per Sistemi Incoerenti: Il metodo proposto NR-SSOR right preconditioned RRGMRES è dimostrato capace di determinare una soluzione di minimi quadrati per arbitrarie $b \in \mathbb{R}^m$ e $A$ singolare, inclusi i casi in cui l'indice di $A \ge 1$ e $R(A) \neq R(A^T)$.
• Estensione ai Problemi Rettangolari: Il metodo è esteso con successo ai problemi di minimi quadrati rettangolari sottodeterminati e sovradeterminati, dove $A$ può essere a rango deficiente.
• Confronto con MINRES-QLP: Il documento stabilisce un quadro di confronto con MINRES-QLP, un metodo noto per gestire sistemi simmetrici singolari, osservando che mentre MINRES-QLP trova soluzioni a norma minima per sistemi coerenti, il metodo proposto offre prestazioni superiori per sistemi incoerenti.

Risultati Numerici
Sono stati condotti estesi esperimenti numerici su:

1. Sistemi Incoerenti GP: Matrici con indice 1 dove $R(A) \cap N(A) = \{0\}$ ma $R(A) \neq R(A^T)$.
2. Sistemi Incoerenti di Indice 2: Matrici dove l'indice è 2.
3. Problemi di Minimi Quadrati Sottodeterminati: Matrici rettangolari di grandi dimensioni (es. Maragal, landmarkT, lp dfl001).

I risultati dimostrano che:

• Convergenza: GMRES standard e RRGMRES applicati direttamente a $Ax=b$ spesso falliscono nel convergere a una soluzione di minimi quadrati per questi sistemi incoerenti e non-range-simmetrici.
• Superiorità di NR-SSOR: Il metodo NR-SSOR preconditioned RRGMRES raggiunge costantemente residui significativamente più piccoli (spesso $10^{-10}$ a $10^{-15}$) rispetto ad altri precondizionatori come $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ o $B = A^T$.
• Efficienza: Il metodo proposto richiede meno iterazioni e un tempo di calcolo significativamente inferiore (fino a 87,9 volte più veloce in specifici casi sottodeterminati) rispetto alle varianti non precondizionate o precondizionate diversamente.
• Confronto con MINRES-QLP: In scenari incoerenti, il metodo proposto ha ottenuto residui ordini di grandezza più piccoli rispetto a MINRES-QLP e ha raggiunto tali minimi in meno iterazioni.

Significatività
Il documento afferma che il metodo NR-SSOR right preconditioned RRGMRES fornisce una soluzione teoricamente giustificata e numericamente robusta per una classe di problemi di algebra lineare difficili: sistemi singolari, non-range-simmetrici e problemi di minimi quadrati rettangolari a rango deficiente. Dimostrando la natura SPD del precondizionatore $C$ derivato da NR-SSOR, gli autori assicurano che il metodo eviti i breakdown associati al GMRES standard in contesti incoerenti. Gli esperimenti numerici validano che questo approccio non è solo teoricamente solido, ma anche praticamente efficiente, superando i metodi esistenti come AB-GMRES con altri precondizionatori e MINRES-QLP in termini di riduzione del residuo e velocità di calcolo per sistemi incoerenti.