Tutorial [Schreibgeschützt]

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