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

Résumé technique : RRGMRES préconditionné à droite par NR-SSOR pour les systèmes non symétriques par rapport à leur image et les problèmes de moindres carrés rectangulaires de rang déficient

Énoncé du problème
La méthode du résidu minimal généralisé (GMRES) est un solveur itératif de sous-espace de Krylov standard pour les systèmes linéaires $Ax = b$. Cependant, lorsque $A$ est singulier et que le système est incohérent (c'est-à-dire $b \notin R(A)$), GMRES est connu pour subir une rupture sans fournir une solution de moindres carrés (LS) à moins que $A$ ne soit symétrique par rapport à son image (EP), ce qui signifie que $R(A) = R(A^T)$. Plus précisément, si $R(A^T) \neq R(A)$ — une condition qui inclut les cas où l'indice de $A$ est supérieur ou égal à 1 — il existe des vecteurs initiaux $x_0$ et des seconds membres $b$ pour lesquels GMRES échoue. De plus, même lorsque $A$ est symétrique par rapport à son image, les sous-problèmes de moindres carrés résolus au sein de GMRES peuvent devenir dangereusement mal conditionnés si $b \notin R(A)$.

Les approches existantes, telles que le GMRES sans rupture (breakdown-free), manquent de garanties théoriques de fonctionnement systématique. De même, bien que la méthode AB-GMRES (appliquant GMRES à $ABz=b$) puisse gérer les systèmes singuliers, les choix standards de préconditionneur $B$ (tels que $B=A^TC$ avec des itérations internes stationnaires) ne garantissent pas que $AB$ soit symétrique par rapport à son image pour les systèmes incohérents, ce qui peut conduire à l'échec de la recherche d'une solution de moindres carrés.

Méthodologie
Les auteurs proposent une méthode itérative robuste combinant trois composantes clés :

1. Préconditionnement à droite avec $B = CA^T$ : Au lieu de résoudre $Ax=b$ directement, la méthode résout un problème de moindres carrés transformé $\min_z \|b - ABz\|_2$ où $B = CA^T$ et $C \in \mathbb{R}^{n \times n}$ est une matrice symétrique définie positive (SPD). Cette transformation garantit que le produit $AB = ACA^T$ est symétrique et symétrique par rapport à son image, quel que soit le fait que $A$ soit ou non symétrique par rapport à son image. Par conséquent, la méthode peut déterminer une solution de LS $x = CA^Tz$ sans rupture pour un $A$ et un $b$ arbitraires.
2. RRGMRES (GMRES à restriction de l'image) : Pour remédier aux problèmes de mauvais conditionnement inhérents à GMRES pour les systèmes incohérents, les auteurs emploient RRGMRES au lieu de GMRES standard. RRGMRES restreint l'espace de recherche à l'image de $A$, offrant une plus grande stabilité pour les systèmes symétriques par rapport à leur image mais incohérents. L'analyse théorique montre que la plus petite valeur singulière de la matrice de Hessenberg dans RRGMRES est bornée inférieurement, une propriété qui n'est pas garantie dans le GMRES standard.
3. Préconditionneur NR-SSOR : L'article introduit l'utilisation de la méthode SSOR non symétrique (NR-SSOR) comme préconditionneur d'itération interne à droite pour construire la matrice $C$. Les auteurs prouvent que si $A$ n'a pas de colonnes nulles et que le paramètre de relaxation $\omega$ satisfait $0 < \omega < 2$, la matrice $C$ résultante (dérivée de l'itération NR-SSOR) est symétrique définie positive. Cette garantie théorique valide l'utilisation de NR-SSOR dans le cadre proposé pour les systèmes singuliers carrés et les problèmes de moindres carrés rectangulaires de rang déficient ($A \in \mathbb{R}^{m \times n}$).

Contributions clés

• Justification théorique : L'article prouve que pour le préconditionneur NR-SSOR à droite $B = CA^T$, la matrice $C$ est SPD sous des conditions standards ($A$ n'a pas de colonnes nulles, $0 < \omega < 2$). Cela garantit que $AB$ est symétrique par rapport à son image, permettant à la méthode de trouver de manière robuste des solutions de LS pour des systèmes non symétriques par rapport à leur image et des problèmes rectangulaires.
• Robustesse pour les systèmes incohérents : Il est démontré que le RRGMRES préconditionné à droite par NR-SSOR détermine une solution de moindres carrés pour tout $b \in \mathbb{R}^m$ et tout $A$ singulier, y compris les cas où l'indice de $A \ge 1$ et $R(A) \neq R(A^T)$.
• Extension aux problèmes rectangulaires : La méthode est étendue avec succès aux problèmes de moindres carrés rectangulaires sous-déterminés et sur-déterminés, où $A$ peut être de rang déficient.
• Comparaison avec MINRES-QLP : L'article établit un cadre de comparaison avec MINRES-QLP, une méthode connue pour gérer les systèmes symétriques singuliers, notant que si MINRES-QLP trouve des solutions de norme minimale pour les systèmes cohérents, la méthode proposée offre des performances supérieures pour les systèmes incohérents.

Résultats numériques
Des expériences numériques approfondies ont été menées sur :

1. Systèmes incohérents GP : Matrices d'indice 1 où $R(A) \cap N(A) = \{0\}$ mais $R(A) \neq R(A^T)$.
2. Systèmes incohérents d'indice 2 : Matrices où l'indice est de 2.
3. Problèmes de moindres carrés sous-déterminés : Grandes matrices rectangulaires (ex. Maragal, landmarkT, lp dfl001).

Les résultats démontrent que :

• Convergence : Le GMRES et le RRGMRES appliqués directement à $Ax=b$ échouent souvent à converger vers une solution de moindres carrés pour ces systèmes incohérents et non symétriques par rapport à leur image.
• Supériorité de NR-SSOR : Le RRGMRES préconditionné par NR-SSOR atteint systématiquement des résidus nettement plus faibles (souvent de $10^{-10}$ à $10^{-15}$) par rapport à d'autres préconditionneurs comme $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ ou $B = A^T$.
• Efficacité : La méthode proposée nécessite moins d'itérations et beaucoup moins de temps de calcul (jusqu'à 87,9 fois plus rapide dans certains cas sous-déterminés) par rapport aux variantes non préconditionnées ou préconditionnées différemment.
• Comparaison avec MINRES-QLP : Dans les scénarios incohérents, la méthode proposée a obtenu des résidus de plusieurs ordres de grandeur inférieurs à ceux de MINRES-QLP et a atteint ces minima en moins d'itérations.

Signification
L'article affirme que le RRGMRES préconditionné à droite par NR-SSOR fournit une solution théoriquement justifiée et numériquement robuste pour une classe de problèmes d'algèbre linéaire difficiles : les systèmes singuliers non symétriques par rapport à leur image et les problèmes de moindres carrés rectangulaires de rang déficient. En prouvant la nature SPD du préconditionneur $C$ dérivé de NR-SSOR, les auteurs garantissent que la méthode évite les ruptures associées au GMRES standard dans les contextes incohérents. Les expériences numériques valident que cette approche est non seulement théoriquement solide mais aussi pratiquement efficace, surpassant les méthodes existantes comme AB-GMRES avec d'autres préconditionneurs et MINRES-QLP en termes de réduction de résidu et de vitesse de calcul pour les systèmes incohérents.