Actuellement dans l'industrie automobile, en médecine ou astrophysique, les problèmes complexes de calculs de structures et de reconnaissance de forme sont résolus sur des calculateurs parallèles composés de centaines de nœuds de calcul. Leurs fonctionnements nécessitent l’utilisation de méthodes de décomposition de domaines. Les premiers modèles de ces méthodes ont été établis par H.A. Schwarz. Le principe consiste à morceler un problème de grande taille en une suite de sous-problèmes de taille plus petite, et donc plus facilement résolus. Depuis leur apparition, les approches ont évolué et des variantes se sont greffées aux modèles de base, aboutissant à différentes qualités de convergence.
Within the automobile industry, the medical sector or in astrophysics the complex problems of structure calculations and shape recognition are currently solved on parallel calculators composed of hundreds of calculation nodes. The way in which they function requires the use of domain decomposition methods. The first models regarding such methods were defined by H.A. Schwarz. The main principle consists in the breaking down of a large scale problem into a series of smaller problems which thus become easier to solve. Since their creation, these approaches have evolved and variations have been added to the basic models thus leading to various convergence qualities.
Auteur(s)
Martin J. GANDER
: Professeur de mathématiques - Section de Mathématiques, Université de Genève
Laurence HALPERN
: Professeur de Mathématiques - Laboratoire Analyse, Géométrie et Applications, Université Paris 13
INTRODUCTION
Tous les problèmes d’ingénierie aujourd’hui sont résolus en parallèle sur des ordinateurs composés de centaines, voire des milliers de noeuds de calcul. Cet article se propose d’exposer les méthodes de décomposition de domaine susceptibles de s’appliquer à ces nouveaux outils. Emile Picard nous enseigne dans que pour comprendre une théorie, il est bon d’avoir en tête un problème modèle.
Les méthodes d’approximation dont nous faisons usage sont théoriquement susceptibles de s’appliquer à toute équation, mais elles ne deviennent vraiment intéressantes pour l’étude des propriétés des fonctions définies par les équations différentielles que si l’on ne reste pas dans les généralités et si l’on envisage certaines classes d’équations.
Nous choisirons donc dans tout cet exposé un fil conducteur, l’équation de la chaleur
( 1 )
représentant les variations en temps et en espace de la température d’un corps emplissant le domaine Ω, soumis à une source de chaleur f (qui sera appelée second membre), avec une température initiale donnée dans tout le domaine, et des conditions aux limites sur le bord du domaine ∂Ω, par exemple de Dirichlet (la température est fixée), soit u = g. ∂tu est la dérivée en temps de u, Δ est l’opérateur de Laplace, Δu = ∂11u + ∂22u + ∂33u. Pour calculer sur un ordinateur une solution approchée de cette équation, on peut commencer par une semi-discrétisation en temps. Le schéma le plus simple est le schéma d’Euler implicite (voir [AF 1 220]). Partageons l’intervalle de temps [0, T] en sous-intervalles [tn, tn+1] de longueur Δt. Notons un(x) l’approximation de u à l’instant tn au point x, calculée par la formule de récurrence
où fn+1 représente f (x, tn+1). Pour passer du temps tn au temps tn+1, il faut donc résoudre l’équation elliptique
dans le domaine Ω, où f est maintenant une fonction indépendante du temps.
La discrétisation en espace de cette équation par une méthode de type éléments finis ou volumes finis mène à un système linéaire (voir [AF 500] et [AF 503]). Lorsque la taille du domaine de calcul est très grande, ou la discrétisation très fine, la taille du système linéaire excède les capacités de stockage et de calcul d’un seul ordinateur, si puissant soit-il. L’idée la plus simple pour remédier à ce problème est de décomposer le système linéaire en sous-systèmes, dont chacun est suffisamment petit pour être résolu très rapidement sur un nœud d’un système d’ordinateurs (divide et impera). Cela peut se faire au niveau purement informatique, mais il est plus fructueux de revenir en amont et de développer une stratégie au niveau du problème mathématique. Cette démarche est souvent réclamée par la géométrie elle-même (assemblage de structures par exemple). Le domaine de calcul est alors partagé en sous-domaines, chacun assigné à un nœud de la grappe de calcul. Les échanges entres les sous-domaines sont effectués par des conditions de transmission et traduits par des échanges entre les processeurs. La résolution du problème de départ est alors réalisée en itérant entre les sous-domaines, et les sous-domaines peuvent même être en espace-temps.
Toutes ces méthodes sont des méthodes de décomposition de domaines. Elles ont pour fondateur H.A. Schwarz qui en écrivit une première version en 1870 . Elles ont donné lieu à une intense activité scientifique depuis l’avènement des calculateurs parallèles. Elles sont utilisées pour des calculs de pneumatiques, d’automobiles, de structures sismiques, de navette spatiale, de reconnaissance de forme, d’environnement, de météorologie, d’astrophysique, de médecine, et tant d’autres.
Leur champ d’utilisation est même plus large : si par exemple le modèle a des propriétés physiques différentes dans différentes parties du domaine, les méthodes de décomposition de domaines sont un outil naturel pour leur traitement. Mentionnons par exemple la jonction d’une poutre et d’une plaque, le couplage entre l’océan et l’atmosphè
(2) -
BJORHUS (M.) -
Semi-discrete subdomain iteration for hyperbolic systems
-
Tech. Rep. 4, NTNU (1995).
(3) -
BOURGAT (J.-F.), GLOWINSKI (R.), LE TALLEC (P.), VIDRASCU (M.) -
Variational formulation and algorithm for trace operator in domain decomposition calculations
-
in Domain Decomposition Methods, T. Chan, R. Glowinski, J. Périaux, and O. Widlund, eds., Philadelphia, PA, SIAM, pp. 3-16 (1989).
(4) -
CAI (X.-C.), SARKIS (M.) -
A restricted additive Schwarz preconditioner for general sparse linear systems
-
SIAM Journal on Scientific Computing, 21, pp. 239-247 (1999).
(5) -
CHAN (T.F.), MATHEW (T.P.) -
Domain decomposition algorithms
-
in Acta Numerica 1994. Cambridge University Press, pp. 61-143 (1994).