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

13

Multigrid (MG) pode ser usado para resolver um sistema linear construindo um palpite inicial e repetindo o seguinte para até a convergência:UMAx=bx0 0Eu=0 0,1 ..

  1. Calcule o residualrEu=b-UMAxEu
  2. Aplique um ciclo multigrid para obter uma aproximação , onde Ae_i = r_i .ΔxEueEuUMAeEu=rEu
  3. A atualização xEu+1xEu+ΔxEu

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 rEu para produzir ΔxEu . Normalmente, é um ciclo V ou um ciclo W. Como é uma operação linear, escrevemos ΔxEu=BrEu .

Pode-se interpretar esse processo como uma iteração pré-condicionada de Richardson. Ou seja, atualizamos xEu+1xEu+BrEu .

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?

Patrick Sanan
fonte
2
(F) MG é bastante sensível; se um modo não é adequadamente amortecido pela correção mais suave ou de dois níveis, tudo fica paralisado. O método de Krylov pode ajudar a atenuar esses modos problemáticos. Por isso, é motivado principalmente pela robustez, pelo que entendi.
chris

Respostas:

10

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-UMAx

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.BUMA

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)

Patrick Sanan
fonte