método multigrid para resolver PDE

15

Preciso de uma explicação simples do método Multigrid ou de alguma literatura sobre isso.

Eu estou familiarizado com métodos iteracionais, incluindo BiCGStab, CG, GS, Jacobi e pré-condicionamento, mas sou iniciante no método multigrid.

Alguém pode explicar isso em detalhes ou pelo menos fornecer claramente pseudocódigo ou código-fonte, mesmo com boa literatura para iniciantes? Obrigado!

Nurlan
fonte

Respostas:

15

A principal idéia por trás do multigrid é a projeção. Eu tento pensar sobre isso da seguinte maneira:

Suponha que eu queira resolver um PDE com muita precisão, por isso procuro discretizar o domínio (digamos, usando o método das diferenças finitas) em uma grade muito fina com muitos e muitos pontos. No final, configurei meu sistema de equações e estou pronto para resolvê-lo. Eu tento usar o meu solucionador iterativo favorito (jacobi, gauss seidel, gradiente conjugado, etc ...). Eu espero mais de um dia e percebo que meu computador ainda está tentando calcular a resposta !!!

A razão pela qual esses métodos iterativos não estão funcionando rapidamente é porque (geralmente) quando você configura um grande sistema de equações como essa, a própria matriz tem valores próprios extremamente próximos de 1. Por que isso importa? Como a taxa de convergência de muitos métodos iterativos está inversamente relacionada ao maior autovalor (consulte o link de Christian Clason para os slides do tutorial Multigrid de Brigg, parte 1, página 27). Portanto, quanto mais próximo estiver o maior valor próprio de 1, mais lento será o método iterativo. (Observação: isso simplifica um pouco demais as coisas, mas ajuda a motivar a necessidade de multigrid).

Obviamente, é sempre mais rápido resolver o problema se houver menos incógnitas (ou seja, em uma grade grossa com menos pontos de grade). Mais importante, porém, a solução (ou solução aproximada) em uma grade mais grossa é um bom ponto de partida para resolver o problema em uma grade mais fina. Essa é a ideia principal por trás da maioria dos métodos multigrid (se não todos). Por que esse é o caso? Intuitivamente, faz sentido, mas existe uma maneira matematicamente rigorosa de justificar isso.

Vejamos os quatro modos do erro em um método iterativo (por razões de argumento, digamos jacobi ou gauss seidel) aplicado ao problema original da grade fina. Veríamos que, nas primeiras iterações, a maioria dos erros de alta frequência (altamente oscilatórios) é removida! Isso é ótimo, mas há um erro de baixa frequência (menos oscilatório) que ainda permanece e não desaparece rapidamente. De fato, é o erro de baixa frequência que impede que um método iterativo padrão converja rapidamente.

quando resolvemos o problema em uma grade mais grossa (digamos, por um método iterativo como jacobi ou gauss-seidel), somos essencialmente capazes de remover erros de frequência mais baixa muito mais rapidamente (ou seja, em menos iterações) do que na grade fina . Portanto, se resolvermos o problema de uma grade grossa, teremos uma solução cujos erros de menor frequência foram significativamente reduzidos. Assim, seria útil como ponto de partida para um método iterativo na grade mais fina.

Embora existam métodos multigrid diferentes, a maioria deles opera com algumas variações do seguinte:

  1. Comece com o problema de grade fina
  2. Projeto em uma grade grossa (também conhecida como restrição )
  3. Aproximar a solução na grade grossa (usando outro solucionador)
  4. Projete a solução de grade grossa na grade mais fina (também conhecida como prolongamento )
  5. Usando a projeção de 4. como um palpite inicial, resolva o problema da grade fina por um método iterativo.

Para mim, a parte mais difícil do método multigrid é as projeções entre grades. Os tutoriais de Briggs sugeridos por @ChristianClason lidam com esse assunto muito melhor do que eu.

Paulo
fonte
Obrigado pela resposta detalhada! Agora eu tenho algum conhecimento básico sobre o método multigrdi. Agora eu tenho uma pergunta específica sobre processos de restrição e prolongamento. Eu li que algumas Matrizes de Restrição R e Matrizes de Interpolação M e fórmulas como A2 = RAI costumavam fazer projeções entre grades. Mas eu não entendi como construir matrizes R e eu ... Existe alguma idéia sobre isso?
Nurlan
Veja os slides 45-57 do tutorial multigrid de Briggs (parte 1) que ChristianClason postou. Lá, Briggs descreve o processo para o Método Multigrid Geométrico. Essa é a explicação mais simples que posso encontrar. Se você tiver mais perguntas, sinta-se à vontade para postar uma nova pergunta! :)
Paul
15

Este site possivelmente não é um bom lugar para pedir uma explicação detalhada com pseudocódigo (como indicado na FAQ , "Se você pode imaginar um livro inteiro que responda à sua pergunta, você está pedindo demais."), Então você pode querer para começar com um dos livros clássicos sobre esse tópico (listado abaixo) e voltar com perguntas específicas sobre detalhes concretos com os quais você tem problemas.

Christian Clason
fonte
2
Briggs é realmente bom!
precisa saber é o seguinte
5

Outro clássico:

  • Wesseling, Uma Introdução aos Métodos Multigrid, John Wiley & Sons, 1992.

Exemplos de códigos podem ser encontrados na MGNet

chris
fonte