Cours de simulation distribueel

Description

1SuP GaliléeL’école d’ingénieurs de l’Institut GaliléeSpécialité MACS 3ème annéeSIMULATION DISTRIBUEEL. Halpern et J. Ryanc INSTITUTGALILEE,99avenueJean-Baptiste-Clément93430 VILLETANEUSE2008/20092Ingénieurs P.U.F. MasterMathématiques appliquées Ho Chi Minh Universityet Calcul Scientifique of Natural SciencesThis course has been given in the years 2007-2009asa graduate course attheUniversity Paris13,intheengineering schoolofappliedmathematicsandscientific computation Sup Galilée, and at the Ho Chi Minh City Universityof Natural Sciences, hosted by the PUF in the department of mathematics.The authors are very grateful to Pr. Zinsmeister for the programm, andto Pr. Duc for his thorough training of the students, and warm welcome inHCMCity.Table des matières1 Foreword 72 Multigrid methods 92.1 Modal analysis in a simple case . . . . . . . . . . . . . . . . . 92.1.1 Simple methods . . . . . . . . . . . . . . . . . . . . . . 102.1.2 Convergence rate . . . . . . . . . . . . . . . . . . . . . 112.1.3 The V- cycle process . . . . . . . . . . . . . . . . . . . 15∞2.1.4 L estimates . . . . . . . . . . . . . . . . . . . . . . . 212.1.5 Number of elementary operations . . . . . . . . . . . . 222.2 The finite elements multigrid algorithm . . . . . . . . . . . . . 222.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 222.2.2 Discrete norm . . . . . . . . . . . . . . . . . . . . . . . 252.2.3 Definition of the multigrid algorithm . . . . . . . . ...

Informations

• Publié par: Pheyn
• Nombre de lectures: 17
• Langue: English

Extrait

1

SuP Galilée L’école d’ingénieurs de l’Institut Galilée

Spécialité MACS 3ème année

SIMULATION DISTRIBUEE

L. Halpern et J. Ryan

c INSTITUT GALILEE, 99 avenue Jean-Baptiste-Clément 93430 VILLETANEUSE 2008/2009

2

Ingénieurs Mathématiques appliquées et Calcul Scientifique

P.U.F. Master Ho Chi Minh University of Natural Sciences

This course has been given in the years 2007-2009 as a graduate course at the University Paris 13, in the engineering school of applied mathematics and scientific computation Sup Galilée, and at the Ho Chi Minh City University of Natural Sciences, hosted by the PUF in the department of mathematics.

The authors are very grateful to Pr. Zinsmeister for the programm, and to Pr. Duc for his thorough training of the students, and warm welcome in HCMCity.

Table des matières

1 Foreword 2 Multigrid methods 2.1 Modal analysis in a simple case . . . . . . . . . . . . . . . . . 2.1.1 Simple methods . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Convergence rate . . . . . . . . . . . . . . . . . . . . . 2.1.3 The V- cycle process . . . . . . . . . . . . . . . . . . . 2.1.4L ∞ estimates. . . . . . . . . .. . . . . . . . . . . . . 2.1.5 Number of elementary operations . . . . . . . . . . . . 2.2 The finite elements multigrid algorithm . . . . . . . . . . . . . 2.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Discrete norm . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Definition of the multigrid algorithm . . . . . . . . . . 2.2.4 Convergence property of the multigrid algorithm . . . . 2.3 Algebraic Multigrid AMG . . . . . . . . . . . . . . . . . . . .

3

7 9 9 10 11 15 21 22 22 22 25 26 27 32

4

TABLE

DES

MATIÈRES

Bibliographie

[1] S.F. McCormick A. Brandt and J.W. Ruge.Algebraic Multigrid (AMG) for Sparse Matrix Equations and Its Applications, D.J. Evans,. Sparsity ed., Cambridge Univ. Press, 1984. [2] Suzanne.C Brenner and Ridgway Scott.The mathematical theory of finite element methods. Springer-Verlag, 1994. [3] William L. Briggs and Van Emden Henson. A multigrid tutorial. www.llnl.gov/CASC/people/henson/mgtut/ps/mgtut.pdf. [4] Robert D. Falgout.An Introduction to Algebraic Multigrid. Computing in Science and Engineering, 2006. [5] Charles F Loan Gene H Golub.Matrix computations. Johns Hopkins University Press, 1996. [6] Wolfgang Hackbusch.Multigrid methods and applications. Springer- Verlag, 1985. [7] Van Emden Henson. An algebraic multigrid tutorial. www.llnl.gov/CASC/people/henson/presentations/amgtut.pdf. [8] Hans Petter Langtangen and Aslak Tveitog. What is multigrid ? folk.uio.no/infima/doc/mg-underscore-nmfpd.pdf. [9] Patrick Lascaux and R. Theodor.Analyse numérique matricielle appli- quée à l’art de l’ingénieur 2d Méthodes itératives. Masson,, volume 2 ; edition, 1996. [10] Pierre-Arnaud Raviart and Jean-Marie Thomas.Introduction à l’analyse numérique des équations aux dérivées partielles 1988.. Masson, [11] Yousef Saad.Iterative methods for sparse linear systems. 1996. http ://www-users.cs.umn.edu/ saad/books.html. [12] P. Wesseling.An introduction to multigrid methods. Wiley -Interscience, 1992.

5

6

BIBLIOGRAPHIE

Chapitre 1

Foreword

Elliptic and hyperbolic partial differential equations are, by and large, at the heart of most mathematical models used in engineering and physics, giving rise to extensive computations. Often the problems that one would like to solve exceed the capacity of even the most powerful computers, or the time required is too great to allow inclusion of advanced mathematical models in the design process of technical apparatus, from microchips to aircraft, making design optimization more difficult. In this course we shall present two numerical approaches, , Multigrid and Domain Decomposition , taking us one step further towards high performance computing. As it is written at"http ://www.mgnet.org/", a very comprehen- sive repository for information related to these two subjects, "Multigrid has the property of using linear time and space to solve a collection of interesting problems, thus making it a very fast, robust solver. Domain decomposition methods are extremely useful for solving problems on oddly shaped domains or for parallelizing standard iterative methods. "

7

8

CHAPITRE

1.

FOREWORD

Chapitre 2

Multigrid methods

Multigrid methods are a prime source of important advances in algorith- mic efficiency , finding a rapidly increasing number of users. Unlike other known methods, multigrid offers the possibility of solving problems with N unknowns with O(N) work and storage, not just for special cases, but for large classes of problems. It relies on the use of several nested grids. For the modal presentation of the method, we refer to [12],[3], [8]. For the finite element part, we refer to [2].

2.1 Modal analysis in a simple case For details on that one can refer to [12] and [9]. The Poisson equation in one dimension d − d 2 x u 2 =fon(01) with Dirichlet boundary conditionsu(0) =u(1) = 0is discretized by the classical second order finite difference stencil. The interval is split intoN intervals of lengthh= 1N, withx j =hj,j∈[0 N]. The discrete unknown isU= (u 1      u N−1 ) T ∼(u(x 1 )     u(x N−1 )) T . LetAbe the matrix of the system  − 2 1 − 2 1 −1 0  A 1  . .  .  (2.1) . . .  . .  . = h 2 0−1 − 2−1     1 2 The matrixAis tridiagonal, symmetric definite positive, diagonally domi- nant.

9

10CHAPITRE 2. MULTIGRID METHODS The righthand sidebis given by b= (f 1  f 2     f N ) T −1  The discrete problem to be solved isAU=b.

2.1.1 Simple methods There are two families of methods. 1. The direct methods : Gauss,LU, Cholewski. These are exact methods using elimination. They are not convenient for large full systems. 2. The iterative methods (a) The old ones SplittingA=M−N;M U m+1 =N U m +b i. Jacobi :M=Ddiagonal part ofA:U m+1 =J U m +D −1 b J= I−D −1 A. ii. Gauss-Seidel :A=D−E−F M=D−Elower part ofA. (D−E)U m+1 =F U m +b. Let us defineL 1 = (D−E) −1 F. ˆ m+1 = iii. Relaxation :U m+1 obtained by any of the above,U ωU ˆ m+1 + (1−ω)U m . The parameterωis defined such as to improve the convergence . The iteration matrices are L ω = (1−ω)I+ωL 1 if Gauss-Seidel is used J(ω) = (1−ω)I+ωJ= (I−ωD −1 A)if Jacobi is used The error is defined by

e m :=U m −U

the residual is given by r m :=AU m −b=Ae m  (b) The gradient methods are related to the problem of minimiza- tion of the functionE(U) = 2 1 (AU U)−(b U)or the equivalent function(Ae e). The iteration is defined by U m+1 =U m −ω m r m = (I−ω m A)U m +ω m b(2.2)

2.1. MODAL ANALYSIS IN A SIMPLE CASE11 where the parameterω m is again determined so as to improve the performance of the method, it can vary at each step. The optimal parameter is given by kr m k 2 = ω m (Ar m  r m ) which minimizesE(U m )for each m. The conjugate gradient me- thod, instead of updating in the direction of the previous residual, searches in the linear subspace generated by all previous residuals (Krylov type method).  U m+1 =U m −ω m d m m d m =r m + −1    ω m ( = A k d r m m  k k d k r 2 r m m ) −1 k k 2 2 d m (2.3)  (r m+1  d m ) = 0 We will not here consider Krylov methods. All the other iterative methods can be written as U m+1 = (I−ωB −1 A)U m +ωB −1 b The gradient method, or Richardson method, corresponds toB≡I. In the other cases,Bis the preconditioner, defined by 1. Relaxed JacobiB=D −1 ,ω∈(01), 2. SORB= (D−E) −1 ,ω∈(02) 3. Gauss-SeidelB= (D−E) −1 ,ω= 1 In any case, the matrix of the iteration isS=I−ωB −1 A, and we have the recursion relation e m+1 =Se m  It is interesting to consider the convergence properties of theses various iterative methods. 2.1.2 Convergence rate The performances of the method can be estimated by the spectral radius of the iteration matrix. Theorem 2.1 any initial guessThe sequence is convergent forU 0 if and only if the spectral radius ofS=I−B −1 Ais strictly smaller than1.