Méthodes multigrilles

Les méthodes multigrilles accélèrent la résolution des équations aux dérivées partielles (EDP) discrétisées en combinant un lissage peu coûteux sur des grilles fines avec des corrections calculées sur des grilles plus grossières, s'attaquant ainsi à l'erreur à chaque échelle de longueur et atteignant des taux de convergence indépendants de la taille du maillage.

Definition

Une méthode multigrille est un solveur itératif qui représente l'erreur sur une hiérarchie de grilles de différentes résolutions, utilisant une relaxation peu coûteuse pour éliminer les composantes d'erreur oscillatoires sur les grilles fines et des résolutions sur grille grossière pour éliminer les composantes lisses, et ce, de manière récursive à travers toutes les échelles.

Scope

Ce sujet couvre la propriété de lissage des itérations simples, le transfert des résidus et des corrections entre les grilles par restriction et prolongation, les cycles à deux grilles et les cycles multigrilles en V, en W et complets, la comparaison entre les méthodes multigrilles géométriques et algébriques, ainsi que la complexité computationnelle optimale (linéaire) qui fait des méthodes multigrilles un solveur de référence pour les problèmes elliptiques.

Core questions

• Pourquoi les itérations simples réduisent-elles rapidement l'erreur oscillatoire mais lentement l'erreur lisse, motivant ainsi l'utilisation de grilles grossières ?
• Comment les résidus sont-ils restreints aux grilles grossières et les corrections prolongées vers les grilles fines ?
• Comment les cycles multigrilles combinent-ils ces opérations pour atteindre une convergence indépendante du maillage ?
• Comment la méthode multigrille algébrique étend-elle l'idée aux problèmes sans grille géométrique sous-jacente ?

Key theories

Lissage et correction sur grille grossière

Les relaxations classiques, telles que Gauss-Seidel, amortissent rapidement l'erreur de haute fréquence (oscillatoire) mais n'affectent que très peu l'erreur de basse fréquence ; la méthode multigrille exploite cela en transférant l'erreur lisse, à convergence lente, vers des grilles plus grossières où elle apparaît oscillatoire et est réduite à moindre coût.

Complexité optimale indépendante du maillage

L'application récursive du lissage et de la correction sur grille grossière dans des cycles en V ou en W produit des facteurs de convergence bornés indépendamment de la taille de la grille, de sorte que le travail nécessaire pour résoudre un problème avec une tolérance fixe n'augmente que linéairement avec le nombre d'inconnues.

Mechanisms

Un cycle multigrille commence par la relaxation du système sur la grille fine pour lisser l'erreur, calcule le résidu et le restreint à une grille plus grossière où l'équation résiduelle est résolue (récursivement, par le même cycle). La correction de la grille grossière est ensuite prolongée et ajoutée à l'approximation de la grille fine, suivie d'une relaxation supplémentaire. Étant donné que chaque niveau de grille gère les composantes d'erreur pour lesquelles il est le plus efficace, le cycle combiné réduit l'erreur à toutes les échelles en un nombre fixe d'itérations. La méthode multigrille algébrique construit la hiérarchie des grilles et les opérateurs de transfert directement à partir des entrées de la matrice, de sorte qu'aucun maillage géométrique n'est nécessaire.

Clinical relevance

Les méthodes multigrilles comptent parmi les solveurs les plus efficaces pour les grands systèmes creux issus des EDP elliptiques et paraboliques et sont utilisées comme solveur ou comme préconditionneur en dynamique des fluides numérique, en mécanique des structures, en électromagnétisme et en traitement d'images ; leur mise à l'échelle quasi-optimale est essentielle pour les simulations à grande échelle sur les supercalculateurs parallèles.

History

L'idée des multigrilles a été introduite par Fedorenko vers 1961 et développée en une méthode pratique et largement applicable par Achi Brandt dans les années 1970 ; l'analyse de Hackbusch l'a établie sur des bases rigoureuses, et la méthode multigrille algébrique a ensuite étendu sa portée aux problèmes non structurés et non géométriques, consolidant son statut de solveur à complexité optimale.

Key figures

• Radii Fedorenko
• Achi Brandt
• Wolfgang Hackbusch
• Stephen McCormick

Seminal works

• trottenberg2001
• briggs2000

Frequently asked questions

Pourquoi les grilles grossières sont-elles utiles ?

L'erreur lisse qu'une relaxation sur grille fine ne supprime que lentement apparaît oscillatoire sur une grille plus grossière, où la relaxation l'élimine rapidement et à moindre coût. Le passage par des grilles de différentes résolutions élimine ainsi efficacement chaque composante d'erreur.

Quelle est la différence entre les méthodes multigrilles géométriques et algébriques ?

La méthode multigrille géométrique utilise une hiérarchie explicite de maillages plus grossiers dérivée de la géométrie du problème, tandis que la méthode multigrille algébrique construit automatiquement les niveaux grossiers et les opérateurs de transfert à partir de la matrice, la rendant applicable lorsqu'il n'existe pas de hiérarchie de grille naturelle.