É comum não haver verificação de convergência no Multigrid?

12

Acabei de ler o capítulo 3 em "Um tutorial multigrid", de Briggs / Henson / McCormick, link .

O texto é sobre ciclos multigrid, como V-cycle, mu-cycle, FMG. O que chamou minha atenção: na maioria dos procedimentos iterativos, verifica-se se convergiu para a tolerância / precisão desejada e, em caso afirmativo, o procedimento é interrompido. Mas Briggs / Henson / McCormick não usa nenhuma verificação de convergência nos esquemas apresentados. O número de iterações e recursões é apenas codificado e é preciso confiar que o esquema irá convergir.

Então, como isso é feito no Multigrid normalmente? É habitual que o número de iterações / recursões seja apenas codificado? Realmente, receio desperdiçar muito tempo de computação porque sou muito preciso ou, por outro lado, a precisão será baixa em muitos casos quando escolher um número menor de iterações / recursões.

Michael
fonte
A falta de respostas para essa pergunta é realmente surpreendente para mim. Certamente existem alguns usuários muito ativos aqui que têm bastante experiência multigrid em ambientes de pesquisa e / ou produção?
Doug Lipinski
2
Penso que o problema é que a multigrid hoje em dia raramente é usada como solucionadora sozinha (devido à falta de teoria geral da convergência), mas como precondicionadora de um método iterativo mais estabelecido, como CG ou GMRES. Nesse contexto, nenhuma verificação de convergência para multigrid é necessária, pois a iteração externa cuida dela.
Christian Clason

Respostas:

4

Sim, é normal não haver verificações de convergência em MG por alguns motivos. Primeiro, se você usar um número diferente de iterações em cada passagem, o operador MG não será mais linear e você terá que usar algo como FGMRES como um acelerador que possa acomodar um pré-condicionador não linear. Segundo, o FMG é um solucionador exato (reduz o erro abaixo do erro de discretização) quando funciona, portanto, a verificação da convergência introduz uma sincronização cara no algoritmo. Você geralmente verifica no final apenas para verificar a convergência.

Matt Knepley
fonte
Você tem alguma fonte para fazer backup disso? Atualmente, a sua resposta e a outra resposta votada de topo se contradizem diretamente.
Doug Lipinski
1) O livro de Saad é a melhor referência para o uso do FGMRES para acomodar um pré-condicionante em mudança: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Acredito na prova de que o FMG reduz o erro abaixo do erro de discretização com um poder suficientemente poderoso V-ciclo está em Trottenberg e Osterlee, mas eu reproduzir a prova no meu livro: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Definitivamente não. Para escolher um exemplo, o livro Multigrid possui um gráfico na página 53 (Figura 2.10) que mostra a diminuição do resíduo em função do número de ciclos V ou W. Você pararia de andar de bicicleta quando estiver satisfeito com o tamanho do resíduo.

A fonte da sua confusão pode ser porque algumas descrições descrevem apenas um único ciclo V. Em alguns casos limitados, como o multigrid é uma técnica tão poderosa, isso pode gerar uma solução adequada. Além disso, o multigrid pode ser usado como pré - condicionador . Nesse caso, o multigrid é apenas um acelerador e a verificação de convergência ocorre em um nível superior. Mas a verificação sempre deve acontecer em algum lugar.

Aço de Damasco
fonte
1
Você tem alguma fonte para fazer backup disso? Atualmente, a sua resposta e a outra resposta votada de topo se contradizem diretamente.
Doug Lipinski
1

No Multigrid usado como solucionador , geralmente a norma relativa do resíduo é usada como critério de parada. À medida que você diminui essa proporção - a precisão da solução deve aumentar. Além disso, no nível mais grosseiro, os pesquisadores fazem coisas diferentes:

  1. resolver usando um solucionador direto (sem convergência)
  2. use iterações fixas (sem convergência)
  3. use a diferença sucessiva entre iterações como critério de convergência (não é um bom método, pois você pode estar longe da solução)
  4. Novamente, use a norma relativa de residual como critério de parada.

O método 2 listado acima, no nível mais grosseiro, é bom quando o Multigrid é usado como pré-condicionador (os especialistas em Multigrid aqui podem comentar - eu sou iniciante).

Então, em geral, a convergência é usada .

Gaurav Saxena
fonte