Tutorial [Schreibgeschützt]

Sawyung - Administrator

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

28 pages

English

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Informations

Publié par	Sawyung
Nombre de lectures	18
Langue	English

Extrait

Multigrid Tutorial
Multigrid (MG) and Local Refinement for
Elliptic Partial Differential Equations
Klaus Stüben
FhG-SCAI
Schloss Birlinghoven
53754 St. Augustin, Germany
e-mail: Klaus.Stueben@scai.fraunhofer.de
MG_Tutorial-1
Overview
•W hy m ultigrid?
• Basic multigrid principles
• Full multigrid (FMG)
• Nonlinear multigrid (FAS)
• Eigenproblems
• Local Refinements
MG_Tutorial-2Why Multigrid?
MG_Tutorial-3
Why Multigrid?
3O(N )
2Large problems require O(N )
1.5O(N )optimal solvers
One-level
solversOptimal solvers require O(N) log(N)
hierarchical algorithms:
1.2O(N )• Multigrid
• Multilevel
• Multiscale O(N) Optimal
solvers
Log(N)
MG_Tutorial-4
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
MG_Tutorial-5
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))
Buneman
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
membrane
Courtesy of Hoechst ZF
Scientific Computing
MG_Tutorial-7
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
MG_Tutorial-9
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
1
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
MG_Tutorial-11
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!
MG_Tutorial-12
Model Problem: Error Smoothing
Smoothing by
Gauss-Seidel relaxation 21 ee
xy
34 ee
MG_Tutorial-13
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
MG_Tutorial-14
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!
MG_Tutorial-15
Example: Model Problem
Standard coarsening:ΩΩ→hh2
Smoothing: Gauss-Seidel relaxation
Restriction:
„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
Ω
1
MG_Tutorial-17
MG Performance for Model Problem
Time per variable (msec)
5
4
MG3
cg/ILU
2 cg/SGS
1
0
32 64 128 256 512 1024
n
-12Residual reduction: ε = 10
MG_Tutorial-18General Remarks
MG_Tutorial-19
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
• ......
MG_Tutorial-20

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Tutorial [Schreibgeschützt]

YouScribe

Le catalogue

Le service

Les conditions