École thématique "Méthodes multigrilles"

Programme

lundi 17/11

14:00 17:30

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)

MG_Damped_Jacobi.m
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

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

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

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

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.