AM194
Introduction to
Multigrid Methods
Time: MWF, 1-1:50pm
Location: TBD, [Temporarily at Rockefeller
Library, Rm. 409]
Brown University
AM194 1 of 312
Luke Olson
Office: Rm. 323, 182 George St.
Phone: X3-1834
Email: lolson@[Link]
[Link]
Office hours: MW 2-2:50pm, others TBA
Brown University
AM194 2 of 312
APPM 7400-003
Syllabus
• Coursework
– No exams
– Homework exercises & computing assignments
– Project & presentation--joint is OK
– Can tailor some or all work & later lectures to your interests
• Philosophy
– Big on fundamentals, principles, & simple ideas
– Think about the scientific method in general
– Understand by concrete examples & experience
– Know the whole picture
– Ask questions & interject comments
– Make sure I explain what you need
• Text
– A Multigrid Tutorial, 2nd edition, 2nd printing
– Supplemental material as needed
Brown University
AM194 3 of 312
Sources
MGNet [Link]
Newsletter
Software repository
Other texts:
Multigrid, by Trottenburg, et al.
Intro to Multigrid Methods, by
Wesseling [on web]
Mathematics and Comp. Tech… by
Růde
Brown University
AM194 4 of 312
Homework exercises
Due 1 week after the relevant chapter is covered.
[note: these are very much subject to change…see the web for updates!]
1: 3,4
2: 1-3, 8, 10, 13, 18
Brown University
AM194 5 of 312
Computing assignments
•Due 2 weeks after the relevant chapter is covered.
•Start assignments very early: computers are merciless!!!
•Use whatever computing language/platform you like.
2: 20 4: 13, 15 6: 6 by computer!!!
7: Convert your 2-D code developed for Chapter 4
(standard coarsening & point relaxation) to solve (7.14).
Verify the code using ε = 1. Test its performance using
ε = 1/2,1/5, 1/10, 2, 5, 10. Interpret your results.
Brown University
AM194 6 of 312
Project & presentation
Due at the end of the semester.
• I am VERY flexible as to what constitutes a project.
• Think about what has captured your attention.
• See me, but only after you’ve thought a lot about it.
• Computing &/or theory &/or application &/or exploration.
• Presentation = in-class short talk &/or hand-in.
• In-class talk: Prepare! Speak to your peers, not me.
• This is meant to be instructive & FUN!
• Check course web site for a bit more detail.
Brown University
AM194 7 of 312
A Multigrid Tutorial
2nd Edition, 2nd Printing
By
William L. Briggs
CU-Denver
Van Emden Henson
LLNL ← THANKS!
Steve McCormick ← THANKS!
CU-Boulder
Brown University
AM194 8 of 312
Outline
by chapter
1. Model Problems 6. Nonlinear Problems
2. Basic Iterative Methods Full approximation scheme
Convergence tests 7. Selected Applications
Analysis Neumann boundaries
Anisotropic problems
3. Elements of Multigrid
Variable meshes
Relaxation
Variable coefficients
Coarsening
8. Algebraic Multigrid (AMG)
4. Implementation Matrix coarsening
Complexity 9. Multilevel Adaptive Methods
Diagnostics FAC
5. Some Theory 10. Finite Elements
Spectral vs. algebraic Variational methodology
Brown University
AM194 9 of 312
Suggested reading
CHECK MY MG LIBRARY & MGNET REPOSITORY
• A. Brandt, “Multi-level Adaptive Solutions to Boundary Value Problems,”
Math Comp., 31, 1977, pp 333-390.
• A. Brandt, “Multigrid techniques: 1984 guide with applications to
computational fluid dynamics,” GMD, 1984.
• W. Hackbusch, “Multi-Grid Methods & Applications,” Springer, 1985.
• W. Hackbusch & U. Trottenberg, “Multigrid Methods”, Springer-Verlag,
1982.
• S. McCormick, ed., “Multigrid Methods,” SIAM Frontiers in Applied
Math. III, 1987.
• U. Trottenberg, C. Oosterlee, & A. Schüller, “Multigrid,” Academic
Press, 2000.
• P. Wesseling, “An Introduction to Multigrid Methods,” Wylie, 1992.
Brown University
AM194 10 of 312
Multilevel methods have been
developed for...
• PDEs, CFD, porous media, elasticity, electromagnetics.
• Purely algebraic problems, with no physical grid; for
example, network & geodetic survey problems.
• Image reconstruction & tomography.
• Optimization (e.g., the traveling salesman & long
transportation problems).
• Statistical mechanics, Ising spin models.
• Quantum chromo dynamics.
• Quadrature & generalized FFTs.
• Integral equations.
Brown University
AM194 11 of 312
Everyone uses multilevel methods
• Multigrid, multilevel, multiscale, multiphysics, …
Use local “governing rules” on the finest level to
resolve the state of the system at these detailed
scales, but--recognizing that these “rules” have
broader implications that are hard to determine
there--use coarser levels to resolve larger scales.
Continual feedback is essential because improving
one scale impacts other scales.
• Common uses
Sight, art, politics, thinking (scientific research),
cooking, team sports, …
Brown University
AM194 12 of 312
1. Model problems
• 1-D boundary value problem:
− u″( x ) + σ u( x ) = f ( x ) 0 < x < 1, σ≥0
u( 0) = u( 1 ) = 0
• Grid:
, xi = ih , i = 0, 1 , . . . N
1
h =
N
x =0 x =1
x0 x1 x2 xi xN
• Let & for .
v i ≈ u( x i ) f i ≈ f ( xi ) i = 0, 1, . . . N
This discretizes the variables, but what about the equations?
Brown University
AM194 13 of 312
Approximate u’’(x) via Taylor series
• Approximate 2nd derivative using Taylor series:
0 h2 h3
0
u( x i + 1 ) = u( x i ) + h u′ ( x i ) + u″ ( x i ) + u′′′ ( x i ) + O( h 4 )
2! 3!
h2 h3
u( x i − 1 ) = u( x i ) − h u′ ( x i ) + u″ ( x i ) − u′′′ ( x i ) + O( h 4 )
2! 3!
• Summing & solving:
u( x i + 1 ) − 2 u( x i ) + u( x i − 1 )
u″ ( x i ) = + O( h 2)
h2
Brown University
AM194 14 of 312
Approximate equation via
finite differences
• Approximate the BVP
− u″( x ) + σ u( x ) = f ( x ) 0 < x < 1, σ≥0
u( 0) = u( 1 ) = 0
by a finite difference scheme:
− vi − 1 + 2 vi − vi + 1
+ σ vi = f i i = 1, 2, . . . N − 1
2
h
v0 = vN = 0
Brown University
AM194 15 of 312
Discrete model problem
Letting T&
v = ( v 1, v 2, . . . , v N − 1 )
T
f = ( f 1, f 2, . . . , f N − 1 )
we obtain the matrix equation Av = f, where A
is (N-1) x (N-1), symmetric, positive definite, &
⎛ 2 + σh2 −1 ⎞ ⎛ f1 ⎞
⎜ ⎟ ⎛ v1 ⎞
⎜ − 1 2 + σh 2 ⎟ ⎜ v2 ⎟ ⎜ f ⎟
−1 ⎜ 2 ⎟
⎜ ⎟ ⎜ ⎟
1 ⎜ 2
− 1 2 + σh − 1 ⎟ ⎜ v3 ⎟ ⎜ f ⎟
A= ⎟, v= ⎜ ⎟, f =⎜ 3 ⎟
2 ⎜
h ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ 2 ⎟ ⎜ N −2⎟
v ⎜ f N −2⎟
⎜ − 1 2 + σ h − 1 ⎟ ⎜v ⎟ ⎜ ⎟
⎜ ⎟ ⎝ N − 1 ⎠ f
⎝ − 1 2 + σh2 ⎠ ⎝ N −1⎠
Brown University
AM194 16 of 312
Stencil notation
A = [-1 2 -1]
dropping h -2 & σ for convenience
Q
-1 Q
-1 Q
Brown University
AM194 17 of 312
Basic solution methods
Method # Ops (2D)
• Direct Gaussian O(N2)
– Gaussian elimination
– Factorization
Elimination
– Fast Poisson solvers (FFT- Jacobi Iter. O(N2 log ε)
based, reduction-based, …)
• Iterative Gauss-Seidel O(N2 log ε)
– Richardson, Jacobi, Gauss-
Seidel, … SOR O(N3/2 log ε)
– Steepest Descent, Conjugate
Gradients, …
– Incomplete Factorization, ... Conjugate O(N3/2 log ε)
Gradient
ICCG O(N5/4 log ε)
FFT O(N log N)
MG-Iterative O(N log ε)
Brown University
MG-Full(FMG) O(N)
AM194 18 of 312
2-D model problem
• Consider the problem
− ux x − uyy + σ u = f ( x , y ) , 0 < x < 1, 0<y<1
u = 0 , x = 0, x = 1, y = 0, y = 1; σ≥0
• Consider the grid
z
1 1
hx = , hy = ,
M N
( x i , yj ) = ( i hx , j hy )
y
0 ≤ i ≤ M
0≤ j ≤ N
Brown University
AM194 x 19 of 312
Discretizing the 2-D problem
• Let v i j ≈ u( x i , yj ) & f i j ≈ f ( xi , yj ) . Again, using 2nd-
order finite differences to approximate u x x & uyy
we arrive at the approximate equation for the
unknown u( x i , yj ) , for i =1,2, … M-1 & j =1,2, …, N-1:
− v i − 1, j + 2v i j − v i + 1, j − v i , j − 1 + 2v i j − v i , j + 1
+ + σ vi j = f i j
hx2 hy2
v i j = 0 , i = 0, i = M , j = 0, j = M
• Ordering the unknowns (& also the vector f )
lexicographically by y-lines:
T
v = (v1,1 , v1,2 ,..., v1,N −1 , v2 ,1 , v2 , 2 ,..., v2 ,N−1 ,..., vM−1,1 ,vM−1,2 ,..., vM−1,N−1 )
Brown University
AM194 20 of 312
Resulting linear system
• We obtain a block-tridiagonal system Av = f :
⎛ A1 − Iy ⎞ v1 ⎛ f1 ⎞
⎜ −I A ⎟ ⎛ ⎞ ⎜ ⎟
− I ⎜ 2 ⎟
⎜ y 2 y ⎟ v f
⎜ 2 ⎟
⎜ − Iy A3 − Iy ⎟ ⎜ v3 ⎟ ⎜ f ⎟
⎜ ⎟ ⎜ ⎟ = ⎜ 3 ⎟
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ − Iy AN − 2 − Iy ⎟ ⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎝ vN − 1 ⎠ ⎜f ⎟
⎝ − I y A N −1 ⎠ ⎝ N −1 ⎠
1
where Iy is a diagonal matrix with on the diagonal
hy2
& 2 2 ⎛ + +σ1
− ⎞
⎜ hx2 hy2 hx2 ⎟
⎜ 1 2 2 1 ⎟
⎜ − 2 2 + 2 +σ − ⎟
⎜ h x hx hy hx2 ⎟
Ai = ⎜ 1 2 2 1 ⎟
− 2 + +σ −
⎜ hx hx2 hy2 hx2 ⎟
⎜ ⎟
⎜ ⎟
⎜ 1 2 2 ⎟
Brown University
− 2 + 2 +σ
AM194
⎝ hx2 hx hy ⎠ 21 of 312
Stencils
preferred for grid issues
Stencils are much better for showing the grid
picture:
again dropping h -2 & σ
⎡0 −1
0 ⎤ • -1• •
⎢ h 2y ⎥
-1 -1
⎢ −12 2 2
2 + 2 +σ
−1 ⎥
• • •
4
⎢ hx h x hy
−1
hx2
⎥
⎢0
⎣ h 2y
0⎥
⎦ • -1• •
Stencils show local relationships--grid point interactions.
Brown University
AM194 22 of 312
M-Matrices
Let A with elements aij be a matrix
Typically symmetric (A=AT) and sparse
Diagonally Dominant: the diagonal is at least as large as the sum of
the off diagonals: n
∑| a
i≠ j
ij |≤|a ii |
Positive Definite: for all u ≠ 0 we have u T Au > 0
A symmetric and DD ⇒ A is positive definite
A SPD, positive diagonal, negative off diagonal entries
⇒
A is an M-matrix
Brown University
AM194 23 of 312
