A Multigrid Tutorial

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

? Model Problems ? Basic Iterative Schemes

? Convergence; experiments ? Convergence; analysis

? Development of Multigrid

? Coarse-grid correction ? Nested Iteration ? Restriction and Interpolation ? Standard cycles: MV, FMG

? Performance

? Implementation ? storage and computation costs

? Performance, (cont)

? Convergence ? Higher dimensions ? Experiments

? Some Theory

? The spectral picture ? The subspace picture ? The whole picture!

? Complications

? Anisotropic operators and grids ? Discontinuous or anisotropic

coefficients ? Nonlinear Problems: FAS

2 of 119

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

? Briggs, "A Multigrid Tutorial," SIAM publications, 1987. ? Briggs, Henson, and McCormick, "A Multigrid Tutorial, 2nd

Edition," SIAM publications, 2000. ? Hackbusch, Multi-Grid Methods and Applications," 1985. ? Hackbusch and Trottenburg, "Multigrid Methods, Springer-

Verlag, 1982" ? St?ben and Trottenburg, "Multigrid Methods," 1987. ? Wesseling, "An Introduction to Multigrid Methods," Wylie,

1992

3 of 119

Multilevel 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 119

Model Problems

? One-dimensional boundary value problem:

- u( x) + u( x) = f ( x) 0 < x < 1, > 0 u( 0) = u( 1) = 0

?

Grid:

h

=

1 N

,

xi = ih ,

i = 0, 1, ... N

x =0

x =1

x0 x1 x2

xi

xN

? Let vi u( xi ) and f i f ( xi ) for i = 0, 1, ... N

5 of 119

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download