méthode multigrille pour résoudre PDE

15

J'ai besoin d'une explication simple de la méthode multigrille ou de la littérature à ce sujet.

Je connais les méthodes itératives dont BiCGStab, CG, GS, Jacobi et le préconditionnement, mais je suis un débutant avec la méthode multigrille.

Quelqu'un peut-il expliquer cela en détail ou au moins fournir clairement un pseudocode ou un code source, même avec une bonne littérature pour les très débutants? Merci!

Nurlan
la source

Réponses:

15

L'idée principale derrière le multigrille est la projection. J'essaie d'y penser comme suit:

Supposons que je veuille résoudre un PDE avec beaucoup de précision, alors je procède à discrétiser le domaine (disons, en utilisant la méthode des différences finies) sur une grille très fine avec beaucoup, beaucoup de points. Au final, j'ai configuré mon système d'équations et je suis prêt à le résoudre. J'essaie d'utiliser mon solveur itératif préféré (jacobi, gauss seidel, gradient conjugué, etc ...). Je continue d'attendre plus d'une journée et je réalise que mon ordinateur essaie toujours de calculer la réponse !!!

La raison pour laquelle ces méthodes itératives ne fonctionnent pas rapidement est que (généralement) lorsque vous configurez un grand système d'équations comme celui-ci, la matrice elle-même a des valeurs propres extrêmement proches de 1. Pourquoi est-ce important? Parce que le taux de convergence de nombreuses méthodes itératives est inversement lié à la plus grande valeur propre (voir le lien de Christian Clason aux Brigid's Multigrid Tutorial Slides, partie 1, page 27). Ainsi, plus la valeur propre est proche de 1, plus la méthode itérative est lente. (Remarque: cela simplifie un peu les choses, mais cela aide à motiver le besoin de multigrilles).

De toute évidence, il est toujours plus rapide de résoudre le problème s'il y a moins d'inconnues (c'est-à-dire sur une grille grossière avec moins de points de grille). Mais plus important encore, la solution (ou la solution approximative) sur une grille plus grossière est un bon point de départ pour résoudre le problème sur une grille plus fine. C'est l'idée clé derrière la plupart (sinon la totalité) des méthodes multigrilles. pourquoi est-ce le cas? Intuitivement, cela a du sens, mais il existe un moyen mathématiquement rigoureux de justifier cela.

Examinons les modes de Fourier de l'erreur dans une méthode itérative (pour les arguments, disons jacobi ou gauss seidel) appliquée au problème de grille fine d'origine. Nous verrions qu'au cours des premières itérations, la plupart des erreurs haute fréquence (hautement oscillatoire) sont supprimées! C'est très bien, mais il y a une erreur de basse fréquence (moins oscillatoire) qui persiste et ne disparaît pas rapidement. En fait, c'est une erreur de basse fréquence qui empêche une méthode itérative standard de converger rapidement.

lorsque nous résolvons le problème sur une grille plus grossière (disons, par une méthode itérative comme jacobi ou gauss-seidel), nous sommes essentiellement capables de supprimer les erreurs de fréquence inférieure beaucoup plus rapidement (c'est-à-dire en moins d'itérations) que sur la grille fine . Donc, si nous résolvons le problème d'une grille grossière, nous avons une solution dont les erreurs de fréquence inférieures ont été considérablement réduites. Ainsi, il serait utile comme point de départ pour une méthode itérative sur la grille plus fine.

Bien qu'il existe différentes méthodes multigrilles, la plupart d'entre elles fonctionnent selon certaines variations suivantes:

  1. Commencez par le problème de la grille fine
  2. Projeter sur une grille grossière (également connue sous le nom de restriction )
  3. Approximer la solution sur la grille grossière (en utilisant un autre solveur)
  4. Projetez la solution de grille grossière sur la grille plus fine (également appelée prolongation )
  5. En utilisant la projection de 4. comme estimation initiale, résolvez le problème de la grille fine par une méthode itérative.

Pour moi, la partie la plus difficile de la méthode multigrille est les projections entre les grilles. Les tutoriels Briggs proposés par @ChristianClason traitent ce sujet beaucoup mieux que moi.

Paul
la source
Merci pour la réponse détaillée! Maintenant, j'ai quelques connaissances de base sur la méthode multigrdi. Maintenant, j'ai une question spécifique sur les processus de restriction et de prolongation. J'ai lu que certaines matrices de restriction R et matrice d'interpolation M et des formules comme A2 = RAI avaient l'habitude de faire des projections entre les grilles. Mais je n'ai pas compris comment construire les matrices R et I .. Y a-t-il des idées à ce sujet?
Nurlan
Regardez les diapositives 45-57 du tutoriel multigrille Briggs (partie 1) que ChristianClason a publié. Là, Briggs décrit le processus de la méthode multigrille géométrique. C'est l'explication la plus simple que je puisse trouver. Si vous avez d'autres questions à ce sujet, n'hésitez pas à poster une nouvelle question! :)
Paul
15

Ce site n'est peut-être pas un bon endroit pour demander une explication détaillée avec le pseudocode (comme indiqué dans la FAQ , "Si vous pouvez imaginer un livre entier qui répond à votre question, vous en demandez trop."), Alors vous voudrez peut-être pour commencer avec l'un des livres classiques sur ce sujet (énumérés ci-dessous) et revenir avec des questions spécifiques sur les détails concrets avec lesquels vous avez des problèmes.

Christian Clason
la source
2
Briggs est vraiment bon!
vanCompute
5

Un autre classique:

  • Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992.

Des exemples de codes peuvent être trouvés sur MGNet

chris
la source