Como é motivado o Multigrid acelerado por Krylov (usando MG como pré-condicionador)?

Multigrid (MG) pode ser usado para resolver um sistema linear construindo um palpite inicial e repetindo o seguinte para até a convergência:$Ax=b$$x_0$$i=0,1..$

1. Calcule o residual$r_i = b-Ax_i$
2. Aplique um ciclo multigrid para obter uma aproximação , onde Ae_i = r_i .$\Delta x_i \approx e_i$$Ae_i = r_i$
3. A atualização $x_{i+1} \gets x_i + \Delta x_i$

O ciclo multigrid é uma sequência de operações de suavização, interpolação, restrição e resolução exata de grade grossa aplicadas a $r_i$ para produzir $\Delta x_i$ . Normalmente, é um ciclo V ou um ciclo W. Como é uma operação linear, escrevemos $\Delta x_i = B r_i$ .

Pode-se interpretar esse processo como uma iteração pré-condicionada de Richardson. Ou seja, atualizamos $x_{i+1} \gets x_i + B r_i$ .

A iteração de Richardson é um método prototípico do subespaço de Krylov, que sugere o uso de ciclos multigrid para pré-condicionar outros métodos do subespaço de Krylov. Isso às vezes é chamado de multigrid "acelerando" com um método de Krylov ou, alternativamente, pode ser visto como uma escolha de um pré-condicionador para um método de Krylov.

Outra maneira de estender o algoritmo acima é empregar Multigrid completo (FMG). Veja esta resposta para uma descrição concisa.

Em que situações o MG acelerado por Krylov é preferível ao MG ou FMG?

Em alguns casos, (F) MG fornece um algoritmo com propriedades ideais. Por exemplo, o FMG adequadamente ajustado pode resolver alguns problemas elípticos em um pequeno número de "unidades de trabalho", em que uma unidade de trabalho é definida como o esforço computacional necessário para expressar o problema em si - nesse caso, as operações para formar o na melhor grade. Esse é um algoritmo tão eficiente (portanto difícil de bater) que é a base para um benchmark HPC projetado para medir a capacidade máxima de um supercomputador para resolver problemas físicos realísticos ( HPGMG ). Se esse método estiver disponível, é claro que é aconselhável usá-lo.$b-Ax$

No entanto, em muitos casos práticos, um método multigrid ideal ou eficaz não é usado. Isso pode ser porque

• esse método é desconhecido ou indisponível para o problema especificado
• smoothers e operadores intergrid não são suficientes para dar convergência aos livros
• o solucionador de malha grossa é inexato

Nesses casos, a solução pode ser degradada por erros que não são reduzidos como deveria pelo ciclo multigrid. Se esse erro estiver contido em um subespaço de baixa dimensão, no entanto, um método de Krylov pode resolver esse erro em um pequeno número de iterações e, portanto, "limpar" após uma solução multigrid imperfeita. Ou seja, se tiver alguns valores próprios externos, um método de Krylov deve ser capaz de capturar os espaços próprios correspondentes.$BA$

Observe que a escolha de usar um método abaixo do ideal pode resultar em um ciclo multigrid muito "mais barato", a ponto de a aceleração de Krylov compensar. Ou seja, pode haver problemas (e sistemas de computação) em que o MG acelerado por Krylov pode superar o MG. Eu estaria interessado em encontrar um exemplo concreto disso.

(Obrigado a @chris acima e Matt Knepley que mencionaram algumas das opções acima em um tutorial)