Stabilizing randomized GMRES through flexible GMRES

Résumé technique : Stabilisation du GMRES randomisé par le GMRES flexible

Énoncé du problème
L'article aborde le défi de la résolution de grands systèmes linéaires creux $Ax = b$ à l'aide de méthodes d'espaces de Krylov randomisés. Si la randomisation s'est avérée hautement efficace pour l'approximation matricielle de rang faible et les problèmes de moindres carrés surdéterminés, son application aux systèmes linéaires généraux non symétriques est plus difficile. Contrairement aux systèmes surdéterminés, les systèmes linéaires généraux manquent de redondance inhérente, ce qui rend le vecteur solution sensible aux perturbations dans toutes les composantes de la matrice. Par conséquent, « esquisser le problème » est moins viable que « esquisser l'algorithme ».

Les solveurs Krylov randomisés existants, tels que le GMRES esquissé (sGMRES), visent à réduire les coûts coûteux d'orthogonalisation associés au GMRES standard en projetant le problème dans un espace de dimension inférieure à l'aide d'un opérateur d'esquisse $S$. Cependant, le sGMRES souffre de problèmes de stabilité. Plus précisément, lors de l'utilisation de processus d'Arnoldi tronqués pour générer des bases de Krylov non orthogonales, la base peut devenir très mal conditionnée, entraînant une stagnation ou une instabilité numérique. Bien que le redémarrage du sGMRES soit un remède courant, il échoue souvent à converger pour des problèmes difficiles, car la longueur de redémarrage requise pour la convergence peut être prohibitivement grande.

Méthodologie
Les auteurs proposent une approche hybride qui utilise le GMRES flexible (FGMRES) comme enveloppe externe pour stabiliser le GMRES esquissé (sGMRES). La méthodologie centrale comprend les composants suivants :

1. Fondement théorique (borne du résidu du FGMRES) :
   Les auteurs dérivent une nouvelle borne supérieure pratique pour le résidu du FGMRES. En introduisant une version flexible de la méthode d'orthogonalisation complète (FFOM), ils établissent que le résidu du FGMRES à l'itération $m$, noté $\|r_m\|$, est borné par le produit du résidu du FFOM à l'itération précédente et du résidu du préconditionneur interne :
   $$\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$$
   Cette borne implique que si le solveur interne (le préconditionneur) réduit efficacement le résidu, l'itération externe du FGMRES réduira également le résidu global, à condition que les résidus du FGMRES et du FFOM restent comparables. Ce résultat théorique justifie l'utilisation du FGMRES pour garantir des normes de résidu non croissantes, même si le solveur interne est instable.

2. Structure algorithmique (FGMRES-sGMRES) :
   L'algorithme proposé, appelé fastGMRES, fonctionne comme suit :

   • Boucle externe : Exécute des itérations du FGMRES.
   • Boucle interne (Préconditionneur) : À chaque itération externe $j$, le préconditionneur $M_j$ est une solution approximative de $Az = v_j$ calculée via $k$ itérations du sGMRES.
   • Implémentation du sGMRES : Le solveur sGMRES interne construit une base de Krylov $B_k$ en utilisant un processus d'Arnoldi tronqué (orthogonalisation uniquement contre les $t$ derniers vecteurs). La solution $z_j$ est trouvée en minimisant le résidu esquissé $\|S(v_j - Az)\|$ sur l'image de $B_k$.
   • Critères d'arrêt : La boucle interne sGMRES se termine selon trois conditions :
     1. Une limite maximale d'itérations $k_{\max}$ (par exemple, 500) pour contrôler la mémoire.
     2. Un seuil de conditionnement pour la base esquissée $SAB_k$ (par exemple, $10^{15}$) pour prévenir un mauvais conditionnement sévère.
     3. La borne estimée du résidu du FGMRES tombant en dessous de la tolérance cible.

3. Paramétrisation :
   La méthode nécessite un réglage minimal des paramètres. Le paramètre principal est le paramètre de troncature d'Arnoldi $t$. Les auteurs étudient $t=0$ (une base de puissance pure sans orthogonalisation) jusqu'à $t=5$.

Contributions clés

• Mécanisme de stabilisation : L'article démontre que l'encapsulation du sGMRES dans une boucle externe FGMRES stabilise efficacement le solveur randomisé. La boucle externe garantit des normes de résidu non croissantes, surmontant les problèmes de stagnation typiques du sGMRES redémarré.
• Nouvelle borne de résidu : La dérivation de la borne $\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$ fournit une justification théorique de la robustesse de la méthode et offre un outil pratique pour prédire la convergence basée sur les performances du solveur interne.
• Simplicité et robustesse : La méthode proposée « fastGMRES » nécessite très peu d'entrée utilisateur. Contrairement à d'autres méthodes de redémarrage déflé (par exemple, GMRES-SDR ou RGS-GMRES-MDR) qui nécessitent une sélection soigneuse des tailles de sous-espaces et du nombre de vecteurs déflés, fastGMRES fonctionne de manière robuste avec des paramètres fixes ($t=0$ ou petit $t$, dimension d'esquisse fixe).
• Efficacité via $t=0$ : Les auteurs rapportent une découverte contre-intuitive selon laquelle le réglage du paramètre de troncature $t=0$ (aucune orthogonalisation dans la boucle interne) produit souvent les meilleures performances en termes de temps de résolution, en particulier pour les problèmes où les produits matrice-vecteur sont peu coûteux.

Résultats numériques
Les auteurs évaluent la méthode sur plusieurs problèmes difficiles issus de la collection de matrices SuiteSparse et d'autres benchmarks :

• vas stokes 1M : Un problème difficile où le sGMRES redémarré stagne. La version stabilisée par FGMRES converge régulièrement. La méthode surpasse significativement le sGMRES redémarré et est compétitive par rapport à GMRES-SDR et RGS-GMRES-MDR, bien qu'elle nécessite moins de choix de paramètres.
• NACA12 : La méthode converge de manière robuste avec et sans préconditionnement ILU. Notamment, $t=0$ reste la configuration la plus rapide, même pour le cas sans préconditionnement où d'autres méthodes peinent ou dépassent le temps imparti.
• ML Geer : Un problème à grande échelle ($n \approx 1,5$ million). La méthode converge de manière robuste pour tous les $t$ testés, bien que $t=0$ montre un léger retard dans les itérations ultérieures en raison du coût croissant de l'orthogonalisation externe du FGMRES.
• Benchmarking : Dans une comparaison contre BiCGSTAB, GMRES, GMRES-DR et GMRES-SDR sur 10 problèmes, fastGMRES figure parmi les plus fiables. Il échoue à converger dans la limite de temps sur un seul problème (où toutes les autres méthodes ont également échoué), tandis que BiCGSTAB échoue sur deux. Bien que GMRES-SDR avec des paramètres soigneusement réglés soit parfois plus rapide, fastGMRES atteint des performances comparables sans nécessiter de réglage de paramètres.

Signification et revendications
L'article affirme que la combinaison du FGMRES et du sGMRES offre un « solveur randomisé pratique » qui équilibre efficacité, robustesse et facilité d'utilisation. La signification réside dans :

1. Fiabilité : Il garantit des normes de résidu non croissantes, une propriété souvent perdue dans les méthodes Krylov randomisées ou redémarrées.
2. Faible surcharge de réglage : Il élimine le besoin d'une sélection complexe de paramètres (telles que les nombres de déflation ou les longueurs de redémarrage) qui affligent d'autres méthodes Krylov avancées.
3. Efficacité computationnelle : L'efficacité surprenante de $t=0$ suggère que l'évitement des produits scalaires dans la boucle interne peut être hautement bénéfique, en particulier pour le calcul parallèle et les scénarios de précision mixte où la communication pour l'orthogonalisation constitue un goulot d'étranglement.

Les auteurs concluent que si la méthode ne surpasse pas toujours les solveurs existants les mieux réglés, elle offre une alternative hautement compétitive, « configurer et oublier », qui est robuste sur un large éventail de systèmes linéaires difficiles. Un travail futur est suggéré pour explorer des structures FGMRES multi-niveaux afin d'atténuer les coûts d'orthogonalisation de la boucle externe pour des nombres d'itérations très élevés.