Flexible GMRES converges in two phases

Aquí se presenta un resumen técnico detallado del artículo "Flexible GMRES Converges in Two Phases" de Stefan Güttel y Lauri Nyman.

1. Planteamiento del Problema

El algoritmo Flexible GMRES (FGMRES) es un solver iterativo estándar para sistemas lineales a gran escala $Ax=b$ que permite precondicionamiento variable. Esta flexibilidad es crucial cuando el precondicionador $M_j$ es un método iterativo en sí mismo (por ejemplo, en métodos Newton-Krylov) o cuando la matriz $A$ solo es accesible mediante productos matriz-vector.

A pesar de su uso generalizado, la teoría de convergencia de FGMRES sigue siendo poco comprendida, particularmente en lo que respecta a cómo la tolerancia de residuo ($\mu$) del precondicionador interno afecta la convergencia del bucle externo de FGMRES.

• La Brecha: Los límites de convergencia existentes para GMRES estándar se basan en representaciones polinómicas del residuo, las cuales no se cumplen para FGMRES porque el espacio de búsqueda no es un subespacio de Krylov estándar debido a los precondicionadores variables.
• La Pregunta: ¿Converge FGMRES geométricamente a la tasa de la tolerancia del precondicionador $\mu$, o cambia el comportamiento de convergencia a medida que avanzan las iteraciones? ¿Puede el método estancarse?

2. Metodología

Los autores desarrollan un análisis riguroso de convergencia basado en la relación entre FGMRES y el Método de Ortogonalización Completa Flexible (FFOM).

• Derivación de Límites Recursivos:

  • Establecen una relación recursiva entre el residuo de FGMRES ($r^{FG}_m$) y el residuo de FFOM ($r^{FF}_{m-1}$) combinado con el residuo del precondicionador ($r^P_m$).
  • Utilizando la propiedad de que $r^{FG}_m \perp \text{span}(AZ_m)$, derivan la desigualdad:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • Relacionan los residuos de FFOM y FGMRES mediante una identidad geométrica que involucra la razón de los residuos sucesivos de FGMRES, lo que lleva a un límite recursivo sobre el factor de contracción $\gamma_m$:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{donde } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Solución Explícita mediante Polinomios de Chebyshev:

  • Asumiendo un límite uniforme sobre el residuo del precondicionador $\|r^P_j\| \leq \mu$, analizan la relación de recurrencia para los factores de contracción.
  • Al transformar la recurrencia en un sistema lineal, identifican que el producto de los factores de contracción se relaciona con los polinomios de Chebyshev de segunda especie ($U_m$).
  • Esto les permite derivar un límite superior a priori de forma cerrada para la norma del residuo.

• Construcción de Agudeza:

  • Para probar que el límite es "agudo" (no puede mejorarse), los autores construyen contraejemplos específicos. Demuestran que para cualquier sistema lineal y cualquier $\mu \leq 1/2$, existe una secuencia de precondicionadores (y una matriz específica $A$) donde el residuo de FGMRES es exactamente igual al límite superior derivado.

3. Contribuciones Clave

A. El Comportamiento de Convergencia en Dos Fases

El hallazgo central del artículo es que la convergencia de FGMRES está gobernada por dos fases distintas, dependientes de la tolerancia del precondicionador $\mu$:

1. Fase 1 (Convergencia Geométrica Inicial):

   • Para conteos de iteraciones pequeños $m$, la tasa de convergencia es aproximadamente $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • Esta fase domina cuando $\mu$ es pequeño (por ejemplo, $\mu \ll 0.5$).

2. Fase 2 (Deterioro o Estancamiento):

   • A medida que $m$ aumenta, la tasa de convergencia se deteriora desde $\mu$ hacia una nueva tasa asintótica $\nu$.
   • La tasa asintótica viene dada por:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Caso $\mu \leq 0.5$: La tasa $\nu$ es ligeramente mayor que $\mu$ (por ejemplo, si $\mu=0.1$, $\nu \approx 0.1005$). Para $\mu$ muy pequeño, la tasa permanece prácticamente constante. Sin embargo, a medida que $\mu \to 0.5$, la tasa se deteriora significativamente, acercándose a $\nu \approx \sqrt{\mu}$.
   • Caso $\mu > 0.5$: El método puede estancarse o fallar después de una fase inicial de reducción. El "índice de estancamiento" $m^*$ (el número de iteraciones antes del estancamiento) disminuye rápidamente a medida que $\mu$ supera 0.5.

B. El Límite Superior Agudo

Los autores derivan el siguiente límite superior agudo para el residuo en el paso $m$ (asumiendo $\mu \leq 1/2$):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
donde $U_m$ es el polinomio de Chebyshev de segunda especie.

• Este límite es alcanzable: Los autores prueban que existen sistemas lineales y secuencias de precondicionadores donde se cumple la igualdad.
• Esto implica que el límite derivado representa el peor caso posible para FGMRES bajo las suposiciones dadas.

C. Condición de Garantía de Convergencia

El artículo establece un umbral crítico: FGMRES está garantizado para converger a la solución exacta (sin estancamiento) si y solo si $\mu \leq 1/2$.

• Si $\mu > 1/2$, el límite teórico permite el estancamiento, y los autores muestran que el estancamiento puede ocurrir efectivamente en la práctica para sistemas específicos.

4. Resultados y Demostraciones Numéricas

Los hallazgos teóricos se validan mediante experimentos numéricos en MATLAB:

1. Verificación de Agudeza: Un sistema construido de $2500 \times 2500$ con un precondicionador GMRES(100) interno ($\mu=0.5$) mostró que el residuo calculado de FGMRES coincidía exactamente con el límite superior teórico, confirmando que el límite es ajustado.
2. Ilustración del Estancamiento: Para $\mu = 0.55$, el residuo se redujo inicialmente pero se estancó después de 6 iteraciones, coincidiendo con el "índice de estancamiento" predicho.
3. Aplicación del Mundo Real: En una matriz dispersa grande de un problema de Poisson 3D (discretización por elementos finitos), el nuevo límite siguió de cerca el comportamiento de convergencia real de FGMRES-GMRES, demostrando su relevancia práctica incluso para sistemas no construidos.

5. Significado e Implicaciones

• Avance Teórico: Este es el primer trabajo que proporciona un límite superior agudo y alcanzable para FGMRES que cuenta explícitamente con la tolerancia variable del precondicionador. Resuelve el misterio de por qué FGMRES a veces converge más lento de lo esperado a pesar de un buen solver interno.
• Guía Práctica para Ajuste:
  • Si un precondicionador puede ajustarse (por ejemplo, estableciendo un residuo objetivo $\mu$), los resultados sugieren que mantener $\mu \leq 0.5$ es esencial para una convergencia garantizada.
  • Para tolerancias muy ajustadas ($\mu \ll 0.5$), el comportamiento de dos fases es despreciable y el método converge geométricamente a la tasa $\mu$.
  • Para tolerancias más laxas ($\mu \approx 0.5$), los usuarios deben esperar una ralentización en la tasa de convergencia a medida que crece el número de iteraciones.
• Comparación con GMRES Reiniciado: El artículo señala que, aunque el GMRES reiniciado tiene una tasa de convergencia teórica de $O(\mu^j)$, FGMRES a menudo lo supera en la práctica debido a efectos de deflación (el solver interno ve lados derechos deflacionados). Sin embargo, el límite del peor caso para FGMRES es estrictamente peor que el límite de GMRES reiniciado cuando $\mu$ está cerca de 0.5, destacando una compensación entre flexibilidad y estabilidad en el peor caso.
• Limitaciones: El análisis asume que $\|r^P_j\| \leq \mu$ es constante. Los autores reconocen que métodos como "fastGMRES" con sketching aleatorizado pueden tener $\mu$ variable, y extender el análisis a tales casos sigue siendo un desafío abierto.

En resumen, el artículo proporciona una caracterización definitiva de la convergencia de FGMRES, demostrando que opera en dos fases y estableciendo un límite duro ($\mu \leq 0.5$) para la convergencia garantizada, respaldado por límites matemáticos agudos y evidencia numérica.