Tutorial [Schreibgeschützt]
28 Pages

Tutorial [Schreibgeschützt]


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


Multigrid TutorialMultigrid (MG) and Local Refinement forElliptic Partial Differential EquationsKlaus StübenFhG-SCAISchloss Birlinghoven53754 St. Augustin, Germanye-mail: Klaus.Stueben@scai.fraunhofer.deMG_Tutorial-1Overview•W hy m ultigrid?• Basic multigrid principles• Full multigrid (FMG)• Nonlinear multigrid (FAS)• Eigenproblems• Local RefinementsMG_Tutorial-2Why Multigrid?MG_Tutorial-3Why Multigrid?3O(N )2Large problems require O(N )1.5O(N )optimal solversOne-levelsolversOptimal solvers require O(N) log(N)hierarchical algorithms:1.2O(N )• Multigrid• Multilevel• Multiscale O(N) OptimalsolversLog(N)MG_Tutorial-4Computational work per variableModel Problem: 2D Poisson EquationLu =−∆ u + Dirichlet boundary conditionsLu(x,y)=∈f(x,)y (x,)y Ω)Lu(x,y)f(x,)y (x,)y Ω )hh h h−1L O1 M PL = −−14 12h M Ph hM −1 PN Qh 2h=1/n, N=(n-1)Au = fhh hMG_Tutorial-5Model Problem: Solution MethodsMethod: Complexity (accuracy ε):2Gauss Elimination O(N )2Jacobi iteration O(N ) log(ε)2Gauss-Seidel iteration O(N ) log(ε)3/2SOR O(N ) log(ε)3/2Conjugate Gradient O(N ) log(ε)3/2Nested Dissection O(N )5/4ICCG O(N ) log(ε)ADI O(N log(N)) log(ε)FFT O(N log(N))BunemanTotal Reduction O(N)Multigrid (iterative) O(N) log(ε)Multigrid (FMG) O(N)MG_Tutorial-6Quantitative Example: Molecular DynamicsAnalysis of dynamical behavior of biological systemsTime integration:Computation of energy/forces:Lipid-double layermembraneCourtesy of Hoechst ...



Published by
Reads 18
Language English

Multigrid Tutorial
Multigrid (MG) and Local Refinement for
Elliptic Partial Differential Equations
Klaus Stüben
Schloss Birlinghoven
53754 St. Augustin, Germany
e-mail: Klaus.Stueben@scai.fraunhofer.de
•W hy m ultigrid?
• Basic multigrid principles
• Full multigrid (FMG)
• Nonlinear multigrid (FAS)
• Eigenproblems
• Local Refinements
MG_Tutorial-2Why Multigrid?
Why Multigrid?
3O(N )
2Large problems require O(N )
1.5O(N )optimal solvers
solversOptimal solvers require O(N) log(N)
hierarchical algorithms:
1.2O(N )• Multigrid
• Multilevel
• Multiscale O(N) Optimal
Computational work per variableModel Problem: 2D Poisson Equation
Lu =−∆ u + Dirichlet boundary conditions
Lu(x,y)=∈f(x,)y (x,)y Ω)
Lu(x,y)f(x,)y (x,)y Ω )hh h h
−1L O
1 M PL = −−14 1
2h M Ph hM −1 PN Qh 2h=1/n, N=(n-1)
Au = fhh h
Model Problem: Solution Methods
Method: Complexity (accuracy ε):
2Gauss Elimination O(N )
2Jacobi iteration O(N ) log(ε)
2Gauss-Seidel iteration O(N ) log(ε)
3/2SOR O(N ) log(ε)
3/2Conjugate Gradient O(N ) log(ε)
3/2Nested Dissection O(N )
5/4ICCG O(N ) log(ε)
ADI O(N log(N)) log(ε)
FFT O(N log(N))
Total Reduction O(N)
Multigrid (iterative) O(N) log(ε)
Multigrid (FMG) O(N)
MG_Tutorial-6Quantitative Example: Molecular Dynamics
Analysis of dynamical behavior of biological systems
Time integration:
Computation of energy/forces:
Lipid-double layer
Courtesy of Hoechst ZF
Scientific Computing
Quantitative Example: Molecular Dynamics
2MOLMEC: straightforward, O(N ) MOLMEC MEGADYN
P 7,000 atomsMEGADYN: FMM approach, O(N) 550,000 atoms
1 8152 sec ---
2 4481 sec 6305 sec
FMM (Fast Multipole) 3 3056 sec ---
Greengard, Rokhlin 4 2427 sec 3295 sec
6 1769 sec ---Separate short & long range forces:
8 --- 1840 sec• Short-range forces
are updated in each time step
• Long-range forces
Estim. time for 550,000
are treated on "coarser scales"
atoms: 1.5 years!
MG_Tutorial-8Basic Multigrid Principles
Smoothing &
Coarse-grid correction
Model Problem: Gauss-Seidel Relaxation
lexicographic order:
One Gauss-Seidel step:
2uu→ : −−uu+4u−u−u=hfi11,,j ij ij,i++1,j ij,1ij,
or, in terms of the error:
−−vv+40v−v−v=vv→ : i11,,j ij ij,i++11,j ij, h
2 AsymptoticVery slow convergence: ρ=−1(Oh)
convergence factor
The smoother the error, the1Very fast „smoothing“hhvv≈ 101ij ij less efficient a further errorof the error: 4
reduction becomes!1
Averaging of error
MG_Tutorial-10Principle of Error Smoothing
Relaxation methods converge slowly
but smooth the error quickly!
error = superposition of1
low and high frequenciese
low frequencies
(slow reduction)
high frequencies
(fast reduction)
2 3e e
Infinite Grid Smoothing Analysis
Fourier components on infinite grid
||ΘΘ :=max(||,|Θ|)12ixΘ /h (|Θ≤| π )exx :=+x11 22
Amplification factor per relaxation step
ixΘ /hixΘ /h µ()Θ ee
Distinguish low & high frequencies
||Θ< π/2 low (smooth) frequenciesixΘ /he ||Θ≥ π/2 high (non-smooth) frequencies
Smoothing factor Model problem, Gauss-Seidel
* *µµ=≥max{| (ΘΘ)|: | |π/ 2} µ = 0.5, h-independent!
Model Problem: Error Smoothing
Smoothing by
Gauss-Seidel relaxation 21 ee
34 ee
Coarse-Grid Correction
Defect equation:
m m m * mdf=−Au Av =d uu=+vh hhh hh h hhh
Coarse-grid correction:
m +1 mm m uu=+vdf=−Au h h hh hhh
m H m hˆdI: = d vI: = vH h h hHH
restriction m interpolationAv =dHH H
hH−1MI=−IAIAhH, h H H h h ρ()M ≥ 1 !hH,
not full rank
Two-Grid Cycle
ν smoothing steps ν smoothing steps1 2
m +1 mm m uu=+vdf=−Au h h hh hhh
m H m hˆdI: = d vI: = vH h h hHH
restriction m interpolationAv =dHH H
ν hH−1 ν2 1M = S (II− AIA) ShhH, hHhh
ρ()M << 1hH,
independent of h!
Example: Model Problem
Standard coarsening:ΩΩ→hh2
Smoothing: Gauss-Seidel relaxation
„full weighting“−1L O
1 M P−−14 1 121L OL = Ω2h M P hh 12h M PM −1 P 224N Q I =h M Ph 16 M121 PN Qh
−1L O Interpolation:1 M P−−14 1L = Ω2 bilinear2h 2hM P4h M −1 PN Q2h 121O L
1h P M224I = P M2h 4 P121 MQ Nh
MG_Tutorial-16Multigrid Cycle
Recursive extensionν ν1 2
of two-grid cycle
Approximate solution by γ two-grid
cycles using still coarser grids, .....
V-Cycle W-Cycle (γ=2)ν νν νΩ 2 21 14 (γ=1)
ν ν ν ννΩ 1 2 1 23
ν ν νν ν ν ννΩ 1 2 1 2 1 22

MG Performance for Model Problem
Time per variable (msec)
2 cg/SGS
32 64 128 256 512 1024
-12Residual reduction: ε = 10
MG_Tutorial-18General Remarks
MG Components
What is multigrid not?
A particular solver
What is multigrid?
A general strategy for constructing
hierarchical solvers
MG components
• Smoothing process (type, number of steps, ...)
• Coarsening process (type of hierarchy, speed of coarsening, ...)
• Intergrid transfer processes (interpolation, restriction)
• Coarser-level operators
• Coarsest-level solver
• More advanced techniques
• ......