mg-tutorial

Informations

• Publié par: Difef
• Nombre de lectures: 30
• Langue: English

Extrait

A
Multigrid Tutorial
By
William L. Briggs
Presented by
Van Emden Henson
Center for Applied Scientific Computing
Lawrence Livermore National Laboratory
This work was performed, in part, under the auspices of the United States Department of Energy by University
of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48.Outline
•M odel Problems
•P erformance, (cont)
• Basic Iterative Schemes
–Convergence
– Convergence; experiments
– Higher dimensions
– Convergence; analysis
– Experiments
• Development of Multigrid
• Some Theory
– Coarse-grid correction
– The spectral picture
– Nested Iteration
– The subspace picture
– Restriction and Interpolation
–The whole picture!
– Standard cycles: MV, FMG
• Complications
•Performance
– Anisotropic operators and grids
– Implementation
– Discontinuous or anisotropic
coefficients
– storage and computation costs
– Nonlinear Problems: FAS
2 of 119Suggested Reading
•Brandt, “Multi-level Adaptive Solutions to Boundary Value
Problems,” Math Comp., 31, 1977, pp 333-390.
•Brandt, “1984 Guide to Multigrid Development, with
applications to computational fluid dynamics.”
•Brigs, “A Multigrid Tutorial,” SIAM publications, 1987.
nd
• Briggs, Henson, and McCormick, “A Multigrid Tutorial, 2
Edition,” SIAM publications, 2000.
•Hackbusch, Multi-Grid Methods and Applications,” 1985.ackbusch and Trottenburg, “Multigrid Methods, Springer-
Verlag, 1982”
• Stüben and Trottenburg, “Multigrid Methods,” 1987.
• Wesseling, “An Introduction to Multigrid Methods,” Wylie,
1992
3 of 119Multilevel methods have been
developed for...
• Elliptic PDEs
• Purely algebraic problems, with no physical grid; for
example, network and geodetic survey problems.
• Image reconstruction and tomography
• Optimization (e.g., the travelling salesman and long
transportation problems)
• Statistical mechanics, Ising spin models.
• Quantum chromodynamics.
• Quadrature and generalized FFTs.
• Integral equations.
4 of 119Model Problems
• One-dimensional boundary value problem:
− u″( x) +σu( x) = f( x) 0< x < 1, σ> 0
u( 0) = u( 1) = 0
1
h =
, x = ih, i = 0, 1,... N
•Grid:
i
N
x= 1
x= 0
x x x
x x
0 2 i
1 N
f ≈ f( x )
v ≈ u( x )
i = 0, 1,... N
• Let and for
i i
i i
5 of 119We use Taylor Series to derive
an approximation to u’’(x)
• We approximate the second derivative using
Taylor series:
2 3
h h
4
u( x ) = u( x ) + h u′( x) + u″( x ) + u′′′( x ) + O( h )
i+ 1 i i i i
2! 3!
2 3
h h
4
u( x ) = u( x ) − h u′( x) + u″( x ) − u′′′( x ) + O( h )
i− 1 i i i i
2! 3!
• Summing and solving,
u( x ) − 2u( x) + u( x )
i+ 1 i i− 1
2
u″( x ) = + O( h )
i
2
h
6 of 119We approximate the equation
with a finite difference scheme
• We approximate the BVP
− u″( x) +σu( x) = f( x) 0< x < 1, σ> 0
u( 0) = u( 1) = 0
with the finite difference scheme:
− v + 2v − v
i− 1 i i+ 1
+σv = f i = 1, 2,... N− 1
i i
2
h
v = v = 0
0 N
7 of 119The discrete model problem
T
v = ( v , v ,..., v )
• Letting and
1 2 N− 1
T
f = ( f , f ,..., f )
1 2 N− 1
we obtain the matrix equation where A
A v = f
is (N-1) x (N-1), symmetric, positive definite, and
2

2+σh − 1
f

v 1

1


2


f
− 1 2+σh −1
v
2
2



2
v
1
f
3
− 1 2+σh −1
3
A= , v= , f =

2

h

v


N−2
f

2
N− 2
−1 2+σh −1


v

N−1

f
2
N− 1

− 1 2+σh

8 of 119Solution Methods
•Direct
– Gaussian elimination
– Factorization
• Iterative
–Jacobi
–Gaus-Seidel
–C onjugate G radient, e tc.
• Note: This simple model problem can be solved
very efficiently in several ways. Pretend it can’t,
and that it is very hard, because it shares many
characteristics with some very hard problems.
9 of 119A two-dimensional boundary value
problem
• Consider the problem:
< < < <
− u − u +σu = f( x, y) , 0 x 1, 0 y 1
xx yy
u = 0, x= 0, x= 1, y= 0, y= 1; σ> 0
• Where the grid is given:
z
1 1
h = , h = ,
x y
M N
( x , y ) = ( i h , j h )
x y
i j
y
0 ≤ i ≤ M
0 ≤ j ≤ N
10 of 119
x