Description de la formation

Aujourd'hui, les simulations numériques tendent à reproduire des phénomènes physiques de plus en plus complexes, ce qui demande des résolutions toujours plus fines, faisant intervenir plusieurs millions d'inconnues. La résolution des systèmes linéaires qui en découlent requiert non seulement un temps de calcul conséquent mais aussi un espace mémoire important. Dans ce contexte, il est nécessaire d'utiliser des méthodes de résolution efficaces : robustes, rapides, parallèles...

Si les méthodes directes telles que la factorisation LU ou de Cholesky sont appréciées pour leur robustesse, leur utilisation n'est pas envisageable pour de gros systèmes linéaires. En effet, l'espace mémoire requis ainsi que le nombre d'opérations pour réaliser la factorisation augmentent de façon polynomiale en fonction du nombre d'inconnues et de la dimension (2D/3D) du problème. Par ailleurs, ces méthodes ont des caractéristiques intrinsèques qui limitent leur passage à l'échelle.

A l'inverse, les méthodes itératives de type relaxation ou de Krylov peuvent être parallélisées plus facilement et leur empreinte mémoire est moins importante. Elles reposent essentiellement sur des opérations de type produits matrice-vecteur, produits scalaires et additions de vecteurs dont le coût est proportionnel au nombre d'inconnues. Elles sont de plus facilement parallélisables. Cependant, assurer une précision satisfaisante de la solution approchée peut nécessiter un nombre élevé d'itérations car la vitesse de convergence peut dépendre par exemple du conditionnement de la matrice. C'est pourquoi, elles sont le plus souvent utilisées sur un système préconditionné.

Les méthodes multigrilles constituent une autre classe de méthodes que l'on peut considérer comme hybrides de part l'utilisation conjointe des méthodes directes et itératives sur lesquelles elles reposent. Elles permettent alors d'obtenir une solution avec un nombre d'itérations réduit tout en bénéficiant d'une plus grande robustesse sur de nombreuses classes de problèmes. Elles présentent également l'avantage de pouvoir être utilisées aussi bien en solveur qu'en préconditionneur.

Cette école présentera les différentes méthodes multigrilles (géométrique, algébrique,…), leurs principes, les critères permettant de bien choisir les paramètres qui les caractérisent (lisseur, opérateur de projection et de prolongement, niveau de raffinement, ...) et leur implémentation sur architectures parallèles.

Le choix de la thématique de cette école fait suite à de nombreuses demandes remontées lors de précédentes formations organisées par le GdR Calcul. De plus, ces méthodes connaissent aujourd'hui un renouveau car elles peuvent se paralléliser facilement sur les architectures récentes et permettent, de ce fait, de pouvoir résoudre de gros systèmes linéaires creux.

Cette formation s'adresse à toute personne qui est amenée à résoudre de grands systèmes linéaires creux et désireuse de comprendre et d'utiliser les méthodes multigrilles pour les résoudre. Il peut s'agir de chercheurs (doctorants, post-doctorants, chercheurs confirmés) ou d'ingénieurs.

Les cours ne nécessiteront aucun pré-requis important. En revanche, une connaissance de base sur les solveurs classiques tels que factorisation LU, Jacobi, Gauss-Seidel, GMRES, … sera un plus, de même que quelques notions de parallélisme.

Programme

lundi 17/11

14:00 17:30 Pas de support disponible

Méthodes de Krylov et multigrille pour la résolution des systèmes linéaires

`Gérard Meurant `__

On présentera le cadre général des méthodes itératives de Krylov pour la résolution des systèmes linéaires.

On étudiera les principales méthodes: le gradient conjugué (CG), GMRES, BiCG, BiCGStab, QMR, etc... en montrant leurs avantages et inconvénients.

On s'intéressera à leurs propriétés respectives, en particulier en arithmétique à précision finie. On verra ensuite comment accélérer la convergence à l'aide de préconditionnements.

On décrira enfin le cadre général des méthodes multigrilles géométrique et algébrique et leur utilisation comme préconditionnement.

mardi 18/11

09:00 17:30

Introduction to Multigrid Methods -- Fundamental Concepts, Basic Algorithms, Local Mode Analysis

`Irad Yavneh `__ (Technion)

Télécharger le support MG_Damped_Jacobi.m
Télécharger le support MG_Damped_Jacobi.py

In the first session we introduce the fundamental concepts of multigrid computational methods, followed by the classical geometric multigrid algorithm and ending with analytical tools for algorithm development and assessment based on Fourier analysis. We begin with a display of the basic observations that generally underlie multilevel algorithms and identify four essential building blocks that need to be selected. We then show how these ingredients come together in the classical geometric multigrid algorithm for the numerical solution of linear elliptic partial differential equations on rectangular grids. Finally, we introduce a Fourier analysis tool known as Local Mode Analysis (LMA), which allows us to estimate quantitative approximate convergence rates for the multigrid algorithm, and thus to predict its behavior, to debug code, and to skillfully tune parameters.

In the practice session we put theory to the test. Beginning with a basic multigrid solver for the Poisson problem on a square grid (which will be provided), we test its convergence properties in practice, extend it to more general problems, and compare its performance against theoretical predictions based on LMA.

The material in this introduction is summarized in part in the informal paper:

I. Yavneh, "Why multigrid methods are so efficient", Computing in Science and Engineering, 8 (6), 12-22, 2006.

hands-on practice session

"MG_Damped_Jacobi.m" is a MATLAB program that solves the Two-Dimensional Poisson problem on a square using multigrid iterations (V-Cycles), and plots:

  1. the residual norm;
  2. the residual norm reduction factor per iteration;
  3. the final numerical solution.

In the practice session we will modify and develop this program. To make the best of the practice session, it is recommended to examine this code in advance and to make sure it works properly on your computer. To run, enter

MG_Damped_Jacobi(n)

where n is some power of 2, e.g., n = 128. This will solve the problem on a grid of n by n mesh intervals. The code should also run on the freely available packages, such as FreeMat.

mercredi 19/11

09:00 17:30 Pas de support disponible

An Introduction to Algebraic Multigrid Methods Based on Aggregation

`Michael Gee `__ et `Tobias Wiesner `__ (Technische Universität München)

Multigrid Methods provide optimal properties as an iterative solution method for a large class of linear systems. Multigrid methods were originally developed to solve boundary value problems on spatial domains. By choosing a discretization method, such problems become systems of algebraic equations associated with the spatial discretization. Then, in multigrid, the solution to the problem at hand is reconstructed using information from some coarser representation of the problem. It is made use of the fact that simple and cheap iterative smoothing processes are efficient in reducing high-oscillatory error components whereas are not able to address low-frequency errors. By using different resolutions of the problem through multiple grids, one can effectively address all frequencies of the solution.

In contrary to geometric multigrid, where explicit hierarchies of spatial discretizations are utilized, an algebraic multigrid approach is not based on meshes but uses purely algebraic definitions of coarse representations of the fine grid problem. This makes algebraic multigrid an ideal approach to be used on complicated geometries and unstructured meshes, where explicit coarse discretizations are tedious to construct.

In this presentation, the focus will be on so called smoothed aggregation algebraic multigrid methods (SA-AMG). After introducing the principle multigrid idea, notation and framework, the SA-AMG formulation will be discussed with special focus on parallel implementations issues and applicability to a range of problems such as computational structural and fluid dynamics problems. The hands on tutorial allows participants to get acquainted with the open source parallel AMG code MueLu, the choice of its parameters and its behavior by applying it to predefined sample problems.

jeudi 20/11

09:00 17:30 Pas de support disponible

Aggregation-based algebraic multigrid

`Yvan Notay `__ (Université Libre de Bruxelles)

In this lecture, we present algebraic multigrid (AMG) methods based on plain (or unsmoothed) aggregation of the unknowns. We start with some theoretical and practical motivation, and next we discuss how to properly choose the multigrid components in this context (the smoother, the number of smoothing steps, the multigrid cycle). Doing so, we highlight the main differences with respect to geometric multigrid and classical AMG. We finally present the key ideas for an efficient parallelization.

vendredi 21/11

09:30 10:30 Pas de support disponible

Le multigrille pour exploiter pleinement les calculateurs parallèles : expérimentation sur les supercalculateurs Tier0.

Hugues Digonnet (Ecole Centrale de Nantes)

Ce retour d'expérience d'un projet PRACE Cim128ki, est consacré à l'apport des méthodes multigrilles au calcul massivement parallèle. En effet, la puissance délivrée par les supercalculateurs de type Tier0 (Top5 européen avec plusieurs dizaines, voir centaines de milliers de coeurs) est telle que la taille des problèmes traités (taille des systèmes linéaires) est parfaite pour tirer partie de la complexité algorithmique des méthodes multigrilles. Nous présenterons ici les outils développés pour obtenir une version multigrille massivement parallèle. Ceci ira de la génération/adaptation des maillages à la possibilité de visualiser les résultats, en passant par la construction des opérateurs de passage. Enfin, des tests d'efficacité seront présentés sur deux types de supercalculateur Tier0 : Curie Bullx Intel/InfiniBand avec 80 740 coeurs et JuQUEEN IBM BlueGENE/Q avec 458 752 coeurs. L'utilisation conjointe d'une méthode multigrille et du calcul parallèle nous a permis une résolution « record » d'un système linéaire à 100 milliards de degrés de liberté pour les équations de Stokes incompressible avec une formulation éléments finis mixte P1+/P1, et ceci en utilisant la quasi totalité en coeurs et mémoire des supercalculateurs.
11:00 12:30 Pas de support disponible

Multilevel methods : Ready for industry?

Frank Hulsemann (EDF R&D Clamart)

Linear systems that arise in industrial simulations tend to be smaller in size than their counterparts in research, but not necessarily easier to solve. This presentation will review different multilevel methods that have been evaluated at EDF over the last decade. For certain differential operators, they have become the default choice as linear solver. However, for some other applications, the design of a fast and robust method remains an open question -- for now.

Inscription

L'inscription se fait en deux étapes :

L'inscription n'est définitive qu'à réception du dossier complet et du règlement éventuel.

Merci de compléter le dossier d'inscription (doc ou pdf) et de l'adresser avant le 15 octobre 2014 par fax au 01 69 15 67 18, par mail à loic.gouarin@math.u-psud.fr ou par courrier à:

Loïc Gouarin

Laboratoire de Mathématiques

Université Paris Sud

Bâtiment 425

91405 Orsay Cedex

Les frais d'inscription sont gratuits pour les personnels CNRS, les personnels du monde académique non CNRS et les personnels d'un EPIC. Les frais d'inscription pour les personnels du secteur privé sont de 700 euros TTC.

L'inscription comprend les frais d'hébergement en chambre individuelle ainsi que les frais pédagogiques. Les frais de transport des agents CNRS sont pris en charge par la délégation d'origine de l'agent à sa demande. Ils doivent donc pour cela envoyer une copie de leur fiche d'inscription à leur délégation d'origine. Pour les non CNRS, les frais de transport doivent être pris par l'organisme de tutelle ou le laboratoire.

Le nombre de places est limité à 40 participants, les organisateurs se laissent la possibilité de sélectionner les participants en fonction de l'ordre d'arrivée des inscriptions et des renseignements portés sur la fiche d'inscription.

Comité scientifique

  • Thierry Coupez (CEMEF -- MINES ParisTech, Sofia-Antipolis)
  • Martin Gander (Université de Genève)
  • Luc Giraud (INRIA, Bordeaux)
  • Yvan Notay (Université Libre de Bruxelles)
  • François-Xavier Roux (ONERA, Palaiseau)

Comité d'organisation

  • Loïc Gouarin (Laboratoire de Mathématiques d'Orsay)
  • Anne-Sophie Mouronval (MSSMat, Ecole Centrale Paris)
  • Pierre Navaro (IRMA, Strasbourg)
  • Laurent Series (MAS, Ecole Centrale Paris)