Est-il habituel de ne pas avoir de vérification de convergence dans Multigrid?

12

Je viens de lire le chapitre 3 dans "A Multigrid Tutorial" de Briggs / Henson / McCormick, lien .

Le texte concerne les cycles multigrilles tels que le cycle V, le cycle mu, le FMG. Ce qui a attiré mon attention: dans la plupart des procédures itératives, on vérifie si elle a convergé vers la tolérance / précision souhaitée et si c'est le cas, la procédure s'arrête. Mais Briggs / Henson / McCormick n'utilisent aucune vérification de convergence dans les schémas présentés. Le nombre d'itérations et de récursions est simplement codé en dur et il faut croire que le schéma convergera.

Alors, comment cela se fait-il normalement dans Multigrid? Est-il habituel que le nombre d'itérations / récursions soit simplement codé en dur? Je crains vraiment de perdre beaucoup de temps de calcul parce que je suis trop précis ou d'un autre côté, la précision sera médiocre dans de nombreux cas lorsque je choisirai un nombre inférieur d'itérations / récursions.

Michael
la source
L'absence de réponses à cette question me surprend vraiment. Il y a sûrement des utilisateurs très actifs ici qui ont pas mal d'expérience multigrille dans les environnements de recherche et / ou de production?
Doug Lipinski
2
Je pense que le problème est que le multigrille est rarement utilisé de nos jours comme solveur (en raison du manque de théorie de convergence générale, je crois), mais plutôt comme préconditionneur pour une méthode itérative plus établie comme CG ou GMRES. Dans ce contexte, aucun contrôle de convergence pour multigrille n'est nécessaire, car l'itération externe s'en charge.
Christian Clason

Réponses:

4

Oui, il est normal de n'avoir aucun contrôle de convergence dans MG pour plusieurs raisons. Premièrement, si vous utilisez un nombre différent d'itérations à chaque passage, alors l'opérateur MG n'est plus linéaire, et vous devrez utiliser quelque chose comme FGMRES comme accélérateur pouvant accueillir un préconditionneur non linéaire. Deuxièmement, FMG est un solveur exact (réduit l'erreur en dessous de l'erreur de discrétisation) lorsqu'il fonctionne, donc la vérification de la convergence introduit une synchronisation coûteuse dans l'algorithme. Vous vérifieriez généralement à la fin juste pour vérifier la convergence.

Matt Knepley
la source
Avez-vous des sources pour étayer cela? Actuellement, votre réponse et l'autre réponse la plus votée se contredisent directement.
Doug Lipinski
1) Le livre de Saad est la meilleure référence pour utiliser FGMRES pour s'adapter à un préconditionneur changeant: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Je crois que la preuve que FMG réduit l'erreur en dessous de l'erreur de discrétisation avec une puissance suffisamment puissante V-cycle est à Trottenberg et Osterlee, mais je reproduis la preuve dans mon livre: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Définitivement pas. Pour prendre un exemple, le livre Multigrid a un tracé à la page 53 (figure 2.10) qui montre la diminution du résidu en fonction du nombre de cycles V ou W. Vous arrêteriez de pédaler lorsque vous êtes satisfait de la taille du résidu.

La source de votre confusion peut être due au fait que certaines descriptions ne décrivent qu'un seul cycle en V. Dans certains cas limités, parce que la multigrille est une technique si puissante, cela peut générer une solution appropriée. De plus, le multigrille peut être utilisé comme préconditionneur . Dans ce cas, la multigrille n'est qu'un accélérateur et la vérification de la convergence se produit à un niveau supérieur. Mais le contrôle doit toujours avoir lieu quelque part.

Acier Damas
la source
1
Avez-vous des sources pour étayer cela? Actuellement, votre réponse et l'autre réponse la plus votée se contredisent directement.
Doug Lipinski
1

Dans Multigrid utilisé comme solveur , la norme relative du résidu est généralement utilisée comme critère d'arrêt. Lorsque vous diminuez ce rapport, la précision de la solution devrait augmenter. De plus, au niveau le plus grossier, les chercheurs font différentes choses:

  1. soit résoudre à l'aide d'un solveur direct (pas de convergence)
  2. utiliser des itérations fixes (pas de convergence)
  3. utiliser la différence successive entre les itérations comme critère de convergence (pas une bonne méthode car vous pourriez être loin de la solution)
  4. Encore une fois, utilisez la norme relative de résidu comme critère d'arrêt.

Méthode 2 ci - dessus au niveau est bon quand grossier Multigrille est utilisé comme pré-conditionneur (experts multigrilles ici peuvent commenter - Je suis un débutant).

Donc, en général, la convergence est utilisée .

Gaurav Saxena
la source