Cours de simulation distribueel
33 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Cours de simulation distribueel

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
33 Pages
English

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

Subjects

Informations

Published by
Reads 17
Language English

Exrait

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
cINSTITUT 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.4Lestimates. . . . . . . . . .. . . . . . . . . . . . . 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 d2xu2=fon(01)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, withxj=hj,j[0 N]. The discrete unknown isU= (u1     uN1)T(u(x1)     u(xN1))T. LetAbe the matrix of the system 21211 0A1 . . . (2.1). . . . . . = h201211 2 The matrixAis tridiagonal, symmetric definite positive, diagonally domi-nant.
9
10CHAPITRE 2. MULTIGRID METHODS The righthand sidebis given by b= (f1 f2    fN)T 1The 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=MN;M Um+1=N Um+b i. Jacobi :M=Ddiagonal part ofA:Um+1=J Um+D1b J= ID1A. ii. Gauss-Seidel :A=DEF M=DElower part ofA. (DE)Um+1=F Um+b. Let us defineL1= (DE)1F. ˆm+1= iii. Relaxation :Um+1obtained by any of the above,U ωUˆm+1+ (1ω)Um. The parameterωis defined such as to improve the convergence . The iteration matrices are Lω= (1ω)I+ωL1if Gauss-Seidel is used J(ω) = (1ω)I+ωJ= (IωD1A)if Jacobi is used The error is defined by
em:=UmU
the residual is given by rm:=AUmb=Aem(b) The gradient methods are related to the problem of minimiza-tion of the functionE(U) =21(AU U)(b U)or the equivalent function(Ae e). The iteration is defined by Um+1=Umωmrm= (IωmA)Um+ωmb(2.2)
2.1. MODAL ANALYSIS IN A SIMPLE CASE11 where the parameterωmis again determined so as to improve the performance of the method, it can vary at each step. The optimal parameter is given by krmk2 = ωm(Arm rm) which minimizesE(Um)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). Um+1=Umωmdm m dm=rm+1 ωm(=Akdrmmkkdkr2rmm)1kk22dm(2.3) (rm+1 dm) = 0 We will not here consider Krylov methods. All the other iterative methods can be written as Um+1= (IωB1A)Um+ωB1b The gradient method, or Richardson method, corresponds toBI. In the other cases,Bis the preconditioner, defined by 1. Relaxed JacobiB=D1,ω(01), 2. SORB= (DE)1,ω(02) 3. Gauss-SeidelB= (DE)1,ω= 1 In any case, the matrix of the iteration isS=IωB1A, and we have the recursion relation em+1=SemIt 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 forU0if and only if the spectral radius ofS=IB1Ais strictly smaller than1.