Flexible GMRES converges in two phases

1. Énoncé du problème

L'algorithme Flexible GMRES (FGMRES) est un solveur itératif standard pour les systèmes linéaires de grande taille $Ax=b$ qui permet un préconditionnement variable. Cette flexibilité est cruciale lorsque le préconditionneur $M_j$ est lui-même une méthode itérative (par exemple, dans les méthodes Newton-Krylov) ou lorsque la matrice $A$ n'est accessible que via des produits matrice-vecteur.

Malgré son utilisation répandue, la théorie de convergence du FGMRES reste mal comprise, en particulier concernant la manière dont la tolérance de résidu ($\mu$) du préconditionneur interne affecte la convergence de la boucle externe FGMRES.

• Le vide théorique : Les bornes de convergence existantes pour le GMRES standard reposent sur des représentations polynomiales du résidu, qui ne s'appliquent pas au FGMRES car l'espace de recherche n'est pas un sous-espace de Krylov standard en raison des préconditionneurs variables.
• La question : Le FGMRES converge-t-il géométriquement au taux de la tolérance $\mu$ du préconditionneur, ou le comportement de convergence change-t-il au fur et à mesure que les itérations progressent ? La méthode peut-elle stagner ?

2. Méthodologie

Les auteurs développent une analyse de convergence rigoureuse basée sur la relation entre le FGMRES et la Méthode d'Orthogonalisation Complète Flexible (FFOM).

• Déduction d'une borne récursive :

  • Ils établissent une relation récursive entre le résidu FGMRES ($r^{FG}_m$) et le résidu FFOM ($r^{FF}_{m-1}$) combiné au résidu du préconditionneur ($r^P_m$).
  • En utilisant la propriété que $r^{FG}_m \perp \text{span}(AZ_m)$, ils dérivent l'inégalité :
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • Ils relient les résidus FFOM et FGMRES via une identité géométrique impliquant le rapport des résidus FGMRES successifs, conduisant à une borne récursive sur le facteur de contraction $\gamma_m$ :
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{où } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Solution explicite via les polynômes de Tchebychev :

  • En supposant une borne uniforme sur le résidu du préconditionneur $\|r^P_j\| \leq \mu$, ils analysent la relation de récurrence pour les facteurs de contraction.
  • En transformant la récurrence en un système linéaire, ils identifient que le produit des facteurs de contraction est lié aux polynômes de Tchebychev de deuxième espèce ($U_m$).
  • Cela leur permet de dériver une borne supérieure a priori sous forme close pour la norme du résidu.

• Construction de la netteté :

  • Pour prouver que la borne est « nette » (ne peut être améliorée), les auteurs construisent des contre-exemples spécifiques. Ils démontrent que pour tout système linéaire et tout $\mu \leq 1/2$, il existe une séquence de préconditionneurs (et une matrice $A$ spécifique) où le résidu FGMRES égale exactement la borne supérieure dérivée.

3. Contributions clés

A. Le comportement de convergence en deux phases

La découverte centrale de l'article est que la convergence du FGMRES est régie par deux phases distinctes, dépendantes de la tolérance du préconditionneur $\mu$ :

1. Phase 1 (Convergence géométrique initiale) :

   • Pour de petits nombres d'itérations $m$, le taux de convergence est approximativement $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • Cette phase domine lorsque $\mu$ est petit (par exemple, $\mu \ll 0,5$).

2. Phase 2 (Détérioration ou stagnation) :

   • À mesure que $m$ augmente, le taux de convergence se détériore de $\mu$ vers un nouveau taux asymptotique $\nu$.
   • Le taux asymptotique est donné par :
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Cas $\mu \leq 0,5$ : Le taux $\nu$ est légèrement supérieur à $\mu$ (par exemple, si $\mu=0,1$, $\nu \approx 0,1005$). Pour des $\mu$ très petits, le taux reste pratiquement constant. Cependant, lorsque $\mu \to 0,5$, le taux se détériore considérablement, s'approchant de $\nu \approx \sqrt{\mu}$.
   • Cas $\mu > 0,5$ : La méthode peut stagner ou échouer après une phase de réduction initiale. L'« indice d'arrêt » $m^*$ (le nombre d'itérations avant la stagnation) diminue rapidement lorsque $\mu$ dépasse 0,5.

B. La borne supérieure nette

Les auteurs dérivent la borne supérieure nette suivante pour le résidu à l'étape $m$ (en supposant $\mu \leq 1/2$) :
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
où $U_m$ est le polynôme de Tchebychev de deuxième espèce.

• Cette borne est atteignable : Les auteurs prouvent qu'il existe des systèmes linéaires et des séquences de préconditionneurs où l'égalité est vérifiée.
• Cela implique que la borne dérivée représente le pire des cas pour le FGMRES sous les hypothèses données.

C. Condition de garantie de convergence

L'article établit un seuil critique : Le FGMRES est garanti de converger vers la solution exacte (sans stagnation) si et seulement si $\mu \leq 1/2$.

• Si $\mu > 1/2$, la borne théorique permet la stagnation, et les auteurs montrent que la stagnation peut effectivement se produire en pratique pour des systèmes spécifiques.

4. Résultats et démonstrations numériques

Les résultats théoriques sont validés par des expériences numériques dans MATLAB :

1. Vérification de la netteté : Un système construit de $2500 \times 2500$ avec un préconditionneur GMRES(100) interne ($\mu=0,5$) a montré que le résidu FGMRES calculé correspondait exactement à la borne supérieure théorique, confirmant que la borne est serrée.
2. Illustration de la stagnation : Pour $\mu = 0,55$, le résidu a diminué initialement mais a stagné après 6 itérations, correspondant à l'« indice d'arrêt » prédit.
3. Application réelle : Sur une grande matrice creuse issue d'un problème de Poisson 3D (discrétisation par éléments finis), la nouvelle borne a suivi de près le comportement de convergence réel du FGMRES-GMRES, démontrant sa pertinence pratique même pour des systèmes non construits.

5. Importance et implications

• Avancée théorique : Il s'agit du premier travail fournissant une borne supérieure nette et atteignable pour le FGMRES qui prend explicitement en compte la tolérance variable du préconditionneur. Cela résout le mystère de la raison pour laquelle le FGMRES converge parfois plus lentement que prévu malgré un solveur interne performant.
• Guidage pratique pour le réglage :
  • Si un préconditionneur peut être réglé (par exemple, en fixant une tolérance de résidu cible $\mu$), les résultats suggèrent que maintenir $\mu \leq 0,5$ est essentiel pour une convergence garantie.
  • Pour des tolérances très strictes ($\mu \ll 0,5$), le comportement en deux phases est négligeable et la méthode converge géométriquement au taux $\mu$.
  • Pour des tolérances plus lâches ($\mu \approx 0,5$), les utilisateurs doivent s'attendre à un ralentissement du taux de convergence à mesure que le nombre d'itérations augmente.
• Comparaison avec le GMRES redémarré : L'article note que, bien que le GMRES redémarré ait un taux de convergence théorique de $O(\mu^j)$, le FGMRES surpasse souvent ce dernier en pratique en raison des effets de déflation (le solveur interne voit des seconds membres déflectés). Cependant, la borne du pire des cas pour le FGMRES est strictement pire que celle du GMRES redémarré lorsque $\mu$ est proche de 0,5, soulignant un compromis entre flexibilité et stabilité dans le pire des cas.
• Limites : L'analyse suppose que $\|r^P_j\| \leq \mu$ est constant. Les auteurs reconnaissent que des méthodes comme « fastGMRES » avec esquisse aléatoire peuvent avoir un $\mu$ variable, et l'extension de l'analyse à de tels cas reste un défi ouvert.

En résumé, l'article fournit une caractérisation définitive de la convergence du FGMRES, prouvant qu'il opère en deux phases et établissant une limite stricte ($\mu \leq 0,5$) pour une convergence garantie, étayée par des bornes mathématiques nettes et des preuves numériques.