Flexible GMRES converges in two phases

1. Formulação do Problema

O algoritmo Flexible GMRES (FGMRES) é um solver iterativo padrão para sistemas lineares de grande escala $Ax=b$ que permite pré-condicionamento variável. Essa flexibilidade é crucial quando o pré-condicionador $M_j$ é, ele próprio, um método iterativo (por exemplo, em métodos Newton-Krylov) ou quando a matriz $A$ é acessível apenas através de produtos matriz-vetor.

Apesar de seu uso generalizado, a teoria de convergência do FGMRES permanece pouco compreendida, particularmente no que diz respeito a como a tolerância de resíduo ($\mu$) do pré-condicionador interno afeta a convergência do loop externo do FGMRES.

• A Lacuna: As limitações de convergência existentes para o GMRES padrão baseiam-se em representações polinomiais do resíduo, que não se aplicam ao FGMRES, pois o espaço de busca não é um subespaço de Krylov padrão devido aos pré-condicionadores variáveis.
• A Questão: O FGMRES converge geometricamente à taxa da tolerância do pré-condicionador $\mu$, ou o comportamento de convergência muda à medida que as iterações progridem? O método pode estagnar?

2. Metodologia

Os autores desenvolvem uma análise de convergência rigorosa baseada na relação entre o FGMRES e o Método de Ortogonalização Total Flexível (FFOM).

• Derivação de Limites Recursivos:

  • Eles estabelecem uma relação recursiva entre o resíduo do FGMRES ($r^{FG}_m$) e o resíduo do FFOM ($r^{FF}_{m-1}$) combinado com o resíduo do pré-condicionador ($r^P_m$).
  • Usando a propriedade de que $r^{FG}_m \perp \text{span}(AZ_m)$, eles derivam a desigualdade:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • Eles relacionam os resíduos do FFOM e do FGMRES por meio de uma identidade geométrica envolvendo a razão dos resíduos sucessivos do FGMRES, levando a um limite recursivo no fator de contração $\gamma_m$:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{onde } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• Solução Explícita via Polinômios de Chebyshev:

  • Assumindo um limite uniforme no resíduo do pré-condicionador $\|r^P_j\| \leq \mu$, eles analisam a relação de recorrência para os fatores de contração.
  • Ao transformar a recorrência em um sistema linear, eles identificam que o produto dos fatores de contração relaciona-se com os polinômios de Chebyshev do segundo tipo ($U_m$).
  • Isso permite que eles derivem um limite superior a priori de forma fechada para a norma do resíduo.

• Construção de Afiamento (Sharpness):

  • Para provar que o limite é "afiado" (não pode ser melhorado), os autores constroem contra-exemplos específicos. Eles demonstram que, para qualquer sistema linear e qualquer $\mu \leq 1/2$, existe uma sequência de pré-condicionadores (e uma matriz específica $A$) onde o resíduo do FGMRES é exatamente igual ao limite superior derivado.

3. Contribuições Principais

A. O Comportamento de Convergência em Duas Fases

A descoberta central do artigo é que a convergência do FGMRES é governada por duas fases distintas, dependentes da tolerância do pré-condicionador $\mu$:

1. Fase 1 (Convergência Geométrica Inicial):

   • Para pequenos números de iterações $m$, a taxa de convergência é aproximadamente $\mu$.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • Esta fase domina quando $\mu$ é pequeno (por exemplo, $\mu \ll 0,5$).

2. Fase 2 (Deterioração ou Estagnação):

   • À medida que $m$ aumenta, a taxa de convergência deteriora-se de $\mu$ para uma nova taxa assintótica $\nu$.
   • A taxa assintótica é dada por:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • Caso $\mu \leq 0,5$: A taxa $\nu$ é ligeiramente maior que $\mu$ (por exemplo, se $\mu=0,1$, $\nu \approx 0,1005$). Para $\mu$ muito pequeno, a taxa permanece praticamente constante. No entanto, à medida que $\mu \to 0,5$, a taxa deteriora-se significativamente, aproximando-se de $\nu \approx \sqrt{\mu}$.
   • Caso $\mu > 0,5$: O método pode estagnar ou falhar após uma fase inicial de redução. O "índice de estagnação" $m^*$ (o número de iterações antes da estagnação) diminui rapidamente à medida que $\mu$ excede 0,5.

B. O Limite Superior Afiado

Os autores derivam o seguinte limite superior afiado para o resíduo no passo $m$ (assumindo $\mu \leq 1/2$):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
onde $U_m$ é o polinômio de Chebyshev do segundo tipo.

• Este limite é atingível: Os autores provam que existem sistemas lineares e sequências de pré-condicionadores onde a igualdade se mantém.
• Isso implica que o limite derivado representa o pior cenário para o FGMRES sob as suposições dadas.

C. Condição de Garantia de Convergência

O artigo estabelece um limiar crítico: O FGMRES é garantido a convergir para a solução exata (sem estagnação) se e somente se $\mu \leq 1/2$.

• Se $\mu > 1/2$, o limite teórico permite estagnação, e os autores mostram que a estagnação pode, de fato, ocorrer na prática para sistemas específicos.

4. Resultados e Demonstrações Numéricas

As descobertas teóricas são validadas através de experimentos numéricos em MATLAB:

1. Verificação de Afiamento: Um sistema construído de $2500 \times 2500$ com um pré-condicionador GMRES(100) interno ($\mu=0,5$) mostrou que o resíduo calculado do FGMRES coincidiu exatamente com o limite superior teórico, confirmando que o limite é apertado.
2. Ilustração de Estagnação: Para $\mu = 0,55$, o resíduo reduziu-se inicialmente, mas estagnou após 6 iterações, coincidindo com o "índice de estagnação" previsto.
3. Aplicação no Mundo Real: Em uma matriz esparsa grande de um problema de Poisson 3D (discretização por elementos finitos), o novo limite acompanhou de perto o comportamento de convergência real do FGMRES-GMRES, demonstrando sua relevância prática mesmo para sistemas não construídos.

5. Significado e Implicações

• Avanço Teórico: Este é o primeiro trabalho a fornecer um limite superior afiado e atingível para o FGMRES que leva explicitamente em conta a tolerância variável do pré-condicionador. Resolve o mistério de por que o FGMRES às vezes converge mais lentamente do que o esperado, apesar de um solver interno bom.
• Orientação Prática para Ajuste:
  • Se um pré-condicionador pode ser ajustado (por exemplo, definindo uma tolerância de resíduo alvo $\mu$), os resultados sugerem que manter $\mu \leq 0,5$ é essencial para garantir a convergência.
  • Para tolerâncias muito rigorosas ($\mu \ll 0,5$), o comportamento de duas fases é negligenciável, e o método converge geometricamente à taxa $\mu$.
  • Para tolerâncias mais frouxas ($\mu \approx 0,5$), os usuários devem esperar uma desaceleração na taxa de convergência à medida que o número de iterações cresce.
• Comparação com GMRES Reiniciado: O artigo observa que, embora o GMRES reiniciado tenha uma taxa de convergência teórica de $O(\mu^j)$, o FGMRES frequentemente supera-o na prática devido a efeitos de deflação (o solver interno vê lados direitos deflacionados). No entanto, o limite do pior caso para o FGMRES é estritamente pior que o limite do GMRES reiniciado quando $\mu$ está próximo de 0,5, destacando uma compensação entre flexibilidade e estabilidade no pior caso.
• Limitações: A análise assume que $\|r^P_j\| \leq \mu$ é constante. Os autores reconhecem que métodos como "fastGMRES" com sketching aleatório podem ter $\mu$ variável, e estender a análise para tais casos permanece um desafio aberto.

Em resumo, o artigo fornece uma caracterização definitiva da convergência do FGMRES, provando que ele opera em duas fases e estabelecendo um limite rígido ($\mu \leq 0,5$) para a convergência garantida, apoiado por limites matemáticos afiados e evidências numéricas.