Flexible GMRES converges in two phases

1. Enunciato del Problema

L'algoritmo Flexible GMRES (FGMRES) è un risolutore iterativo standard per sistemi lineari su larga scala $Ax=b$ che consente una precondizionamento variabile. Questa flessibilità è cruciale quando il precondizionatore $M_j$ è esso stesso un metodo iterativo (ad esempio, nei metodi Newton-Krylov) o quando la matrice $A$ è accessibile solo tramite prodotti matrice-vettore.

Nonostante il suo ampio utilizzo, la teoria della convergenza di FGMRES rimane scarsamente compresa, in particolare per quanto riguarda come la tolleranza del residuo ($\mu$) del precondizionatore interno influisca sulla convergenza del ciclo esterno FGMRES.

• Il Divario: I limiti di convergenza esistenti per GMRES standard si basano su rappresentazioni polinomiali del residuo, che non valgono per FGMRES perché lo spazio di ricerca non è un sottospazio di Krylov standard a causa dei precondizionatori variabili.
• La Domanda: FGMRES converge geometricamente al tasso della tolleranza del precondizionatore $\mu$, o il comportamento di convergenza cambia man mano che le iterazioni procedono? Il metodo può stagnare?

2. Metodologia

Gli autori sviluppano un'analisi rigorosa della convergenza basata sulla relazione tra FGMRES e il Flexible Full Orthogonalization Method (FFOM).

• Derivazione del Limite Ricorsivo:

  • Stabiliscono una relazione ricorsiva tra il residuo FGMRES ($r^{FG}_m$) e il residuo FFOM ($r^{FF}_{m-1}$) combinato con il residuo del precondizionatore ($r^P_m$).
  • Utilizzando la proprietà che $r^{FG}_m \perp \text{span}(AZ_m)$, derivano la disuguaglianza:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • Relazionano i residui FFOM e FGMRES tramite un'identità geometrica che coinvolge il rapporto tra i residui FGMRES successivi, portando a un limite ricorsivo sul fattore di contrazione $\gamma_m$:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{dove } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Soluzione Esplicita tramite Polinomi di Chebyshev:

  • Assumendo un limite uniforme sul residuo del precondizionatore $\|r^P_j\| \leq \mu$, analizzano la relazione di ricorrenza per i fattori di contrazione.
  • Trasformando la ricorrenza in un sistema lineare, identificano che il prodotto dei fattori di contrazione è correlato ai polinomi di Chebyshev di seconda specie ($U_m$).
  • Questo permette loro di derivare un limite superiore a priori in forma chiusa per la norma del residuo.

• Costruzione della Sharpness (Affilatura):

  • Per dimostrare che il limite è "sharp" (non migliorabile), gli autori costruiscono specifici controesempi. Dimostrano che per qualsiasi sistema lineare e qualsiasi $\mu \leq 1/2$, esiste una sequenza di precondizionatori (e una specifica matrice $A$) in cui il residuo FGMRES uguaglia esattamente il limite superiore derivato.

3. Contributi Chiave

A. Il Comportamento di Convergenza in Due Fasi

La scoperta centrale dell'articolo è che la convergenza di FGMRES è governata da due fasi distinte, dipendenti dalla tolleranza del precondizionatore $\mu$:

1. Fase 1 (Convergenza Geometrica Iniziale):

   • Per piccoli numeri di iterazioni $m$, il tasso di convergenza è approssimativamente $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • Questa fase domina quando $\mu$ è piccolo (ad esempio, $\mu \ll 0.5$).

2. Fase 2 (Deterioramento o Stagnazione):

   • Man mano che $m$ aumenta, il tasso di convergenza si deteriora da $\mu$ a un nuovo tasso asintotico $\nu$.
   • Il tasso asintotico è dato da:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Caso $\mu \leq 0.5$: Il tasso $\nu$ è leggermente maggiore di $\mu$ (ad esempio, se $\mu=0.1$, $\nu \approx 0.1005$). Per $\mu$ molto piccoli, il tasso rimane praticamente costante. Tuttavia, man mano che $\mu \to 0.5$, il tasso si deteriora significativamente, avvicinandosi a $\nu \approx \sqrt{\mu}$.
   • Caso $\mu > 0.5$: Il metodo può stagnare o collassare dopo una fase iniziale di riduzione. L'"indice di arresto" $m^*$ (il numero di iterazioni prima della stagnazione) diminuisce rapidamente man mano che $\mu$ supera 0.5.

B. Il Limite Superiore Sharp

Gli autori derivano il seguente limite superiore sharp per il residuo al passo $m$ (assumendo $\mu \leq 1/2$):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
dove $U_m$ è il polinomio di Chebyshev di seconda specie.

• Questo limite è raggiungibile: Gli autori dimostrano che esistono sistemi lineari e sequenze di precondizionatori in cui vale l'uguaglianza.
• Ciò implica che il limite derivato rappresenta lo scenario peggiore per FGMRES sotto le ipotesi date.

C. Condizione di Garanzia di Convergenza

L'articolo stabilisce una soglia critica: FGMRES è garantito convergere alla soluzione esatta (senza stagnazione) se e solo se $\mu \leq 1/2$.

• Se $\mu > 1/2$, il limite teorico consente la stagnazione, e gli autori mostrano che la stagnazione può effettivamente verificarsi nella pratica per sistemi specifici.

4. Risultati e Dimostrazioni Numeriche

I risultati teorici sono validati attraverso esperimenti numerici in MATLAB:

1. Verifica della Sharpness: Un sistema costruito $2500 \times 2500$ con un precondizionatore GMRES(100) interno ($\mu=0.5$) ha mostrato che il residuo FGMRES calcolato corrispondeva esattamente al limite superiore teorico, confermando che il limite è stretto.
2. Illustrazione della Stagnazione: Per $\mu = 0.55$, il residuo si è ridotto inizialmente ma è stagnato dopo 6 iterazioni, corrispondendo all'"indice di arresto" previsto.
3. Applicazione nel Mondo Reale: Su una matrice sparsa di grandi dimensioni proveniente da un problema di Poisson 3D (discretizzazione agli elementi finiti), il nuovo limite ha tracciato da vicino il comportamento di convergenza effettivo di FGMRES-GMRES, dimostrando la sua rilevanza pratica anche per sistemi non costruiti.

5. Significato e Implicazioni

• Svolta Teorica: Questo è il primo lavoro a fornire un limite superiore sharp e raggiungibile per FGMRES che tiene esplicitamente conto della tolleranza variabile del precondizionatore. Risolve il mistero del perché FGMRES a volte converga più lentamente del previsto nonostante un buon risolutore interno.
• Guida Pratica per la Sintonizzazione:
  • Se un precondizionatore può essere sintonizzato (ad esempio, impostando un residuo target $\mu$), i risultati suggeriscono che mantenere $\mu \leq 0.5$ è essenziale per una convergenza garantita.
  • Per tolleranze molto strette ($\mu \ll 0.5$), il comportamento in due fasi è trascurabile e il metodo converge geometricamente al tasso $\mu$.
  • Per tolleranze più lasche ($\mu \approx 0.5$), gli utenti dovrebbero aspettarsi un rallentamento del tasso di convergenza man mano che il numero di iterazioni cresce.
• Confronto con GMRES Ricominciato: L'articolo nota che, sebbene GMRES ricominciato abbia un tasso di convergenza teorico di $O(\mu^j)$, FGMRES spesso lo supera nella pratica grazie agli effetti di deflazione (il risolutore interno vede vettori di destra deflati). Tuttavia, il limite peggiore per FGMRES è strettamente peggiore del limite di GMRES ricominciato quando $\mu$ è vicino a 0.5, evidenziando un compromesso tra flessibilità e stabilità nel caso peggiore.
• Limitazioni: L'analisi assume che $\|r^P_j\| \leq \mu$ sia costante. Gli autori riconoscono che metodi come "fastGMRES" con sketching randomizzato possono avere $\mu$ variabile, e estendere l'analisi a tali casi rimane una sfida aperta.

In sintesi, l'articolo fornisce una caratterizzazione definitiva della convergenza di FGMRES, dimostrando che opera in due fasi e stabilendo un limite rigido ($\mu \leq 0.5$) per la convergenza garantita, supportato da limiti matematici sharp ed evidenze numeriche.