Advanced Finite Element Methods (MA4303)

• Lecture notes of this course are currently typeset. A preliminary version can be obtained upon request.

Organisatorial

Lecture	Prof. Dr. Thomas Dickopf Fridays, 08:30-10:00 in Room 02.08.011 Last lecture: Friday, 07.02.2014
Office hours	By appointment
Exercises	Prof. Dr. Thomas Dickopf Mondays, 12:15-13:45 in Room 01.06.011, biweekly Last exercises: Monday, 27.01.2014
Exams	The oral exams are scheduled for Thursday, 20.02.2014 All participants have received the schedule.
Tutorial "Parallel Implementation"	For interested students, additional interdisciplinary training for the parallel implementation (with MPI and OpenMP) of the methods treated in the lecture is offered. See here.

Contents

• Module MA4303
• This semester's lecture focuses on the parallel solution of partial differential equations. We will consider selected domain decomposition methods and other parallel solution algorithms for (finite element discretizations of) elliptic and parabolic PDEs.
• Keywords: Parallel numerical linear algebra, block iterative methods, Schwarz methods, mesh partitioning, iterative substructuring, parallel multigrid methods

Lectures

• Chapter 1 Introduction (18.10.2013)
  • 1.1 Parallel computing -> Why? Goals...
  • 1.2 Parallel solution of PDEs
    • Goals...
    • Example I) Overlapping Schwarz method (1D toy problem, continuous)
    • Example II) Parallelizing the Gauß-Seidel method (2D model problem, discrete)
    • Example III) Improving the Jacobi method (2D model problem, discrete) (25.10.2013)
  • 1.3 Analysis of the Schwarz method for a model problem (1st: 1D toy problem, 2nd: 2D model problem, both continuous)
  • 1.4 Non-overlapping domain decomposition methods
    • Dirichlet-Neumann method (continuous)
    • Analysis of 1D toy problem (08.11.2013)
  • 1.5 Parallelization in time: another matter
  • 1.6 Performance and scalability
• Chapter 2 Non-overlapping domain decomposition methods / Iterative substructuring (15.11.2013)
  • 2.1 Recap: Elliptic PDEs and variational formulation
    • Fundamental notations, Lebesgue spaces, Sobolev spaces, weak formulation
  • 2.2 Steklov-Poincaré operator
    • Motivation, formal definition
    • Reinterpretation of the Dirichlet-Neumann algorithm (22.11.2013)
  • 2.3 Variational formulation of the interface equation
    • Trace operators, extension operators
    • Weak Steklov-Poincaré operator
    • Structure/Properties (29.11.2013)
  • 2.4 Finite element approximation of the interface equation
    • Recap: Lagrange FE on simplicial meshes
    • Discrete Steklov-Poincaré equation
    • Matrix representation
    • Schur complement matrix (06.12.2013)
    • Interpretation of discrete Dirichlet-Neumann method
  • 2.5 Condition number estimates
    • Optimality of Dirichlet-Neumann method (13.12.2013)
  • 2.6 "Aha-moments" in Chapter 2 so far
  • 2.7 Iterative substructuring with many subdomains
    • Red-black Dirichlet-Neumann method with crosspoint Schur complement
    • Outlook (20.12.2013)
  • 2.8 Non-conforming domain decomposition
    • Mortar finite element method
    • Dirichlet-Neumann-type method for the mortar discretization
• Chapter 3 The Parareal method (10.01.2014)
  • Excursus on parallelization in time
    • Derivation of the Parareal method as preconditioned Richardson iteration
    • Algorithm in Matlab
    • Theoretical speedup
    • Convergence results (17.01.2014)
• Chapter 4 Overlapping domain decomposition methods / Theory of Schwarz methods
  • 4.1 Subspace correction methods
    • Framework and notations: Subspace solution operators
    • Additive and multiplicative Schwarz methods
    • Examples: (Block) Jacobi and Gauß-Seidel methods
  • 4.2 Abstract convergence theory (24.01.2014)
    • Assumptions with examples
    • Condition number estimate for the additive Schwarz method
  • 4.3 Two-level overlapping Schwarz method (31.01.2014)
    • Construction of the method
    • Assumptions on overlap, domain decomposition and coarse mesh
    • Auxiliary results
    • Condition number estimate (07.02.2014)
  • 4.4 Excursus: Mesh partitioning
  • 4.5 Multilevel Schwarz methods
    • MDS and BPX

Matlab Examples

• schwarz_1d_parabola.m: Overlapping Schwarz method (1D toy problem, continuous)
• rbgs_2d_modelproblem.m: Red-black Gauß-Seidel method (2D model problem)
• blockjacobi_2d_modelproblem.m: Block Jacobi method (2D model problem)
• dirichletneumann_1d_parabola.m: Dirichlet-Neumann method (1D toy problem, continuous)
• robinrobin_1d_parabola.m: Robin-Robin method (1D toy problem, continuous)
• schurcomplement_2d_modelproblem.m: Schur complement (2D model problem)
• condofschurcomplement_2d_modelproblem.m: Condition number of the Schur complement (2D model problem)
• dirichletneumann_2d_modelproblem.m: Dirichlet-Neumann method with illustration of iterates (2D model problem)
• dirichletneumann_2d_modelproblem_manysubdomains.m: Dirichlet-Neumann method with crosspoint Schur complement (2D model problem)
• parareal_1d_exp.m: Parareal method (scalar, linear)
• parareal_1d_hyp.m: Parareal method (scalar, nonlinear)
• twoleveladditiveschwarz_1d_modelproblem.m: Two-level overlapping Schwarz method (1D model problem)

Homework Assignments

• Sheet 1 (Hand in: 04.11.2013)
• Sheet 2 (Hand in: 18.11.2013)
• Sheet 3 (Hand in: 02.12.2013)
• Sheet 4 (Hand in: 16.12.2013)
• Sheet 5 (Hand in: 13.01.2014)
• Sheet 6 (Hand in: 27.01.2014)

Exam Bonus System

• 75% of the homework credits are required to obtain a bonus for the final exam.
• Homework credits are awarded if the lecturer concludes that
  1) the students put serious effort in the solution of the exercise and
  2) the solution catches the main mathematical ideas of the exercise.
  This assessment is typically based on the discussions in the tutorials.
• The bonus improves the final grade by one step, e.g., from 2.3 to 2.0.
• The grade 1.0 cannot be further improved.
• The bonus is only applied, if the exam is passed without (i.e., it does not improve the grades 4.3, 4.7 and 5.0).
• Students should keep their graded assignments to prove their eligibility for the exam bonus.
• Students may submit their homework in teams of two.

Literature & Further Reading

Mainly

• P. Bastian: Parallele adaptive Mehrgitterverfahren, Teubner, 1996
• J. J. Dongarra, I. S. Duff, D. C. Sorensen, H. A. van der Vorst: Numerical Linear Algebra for High Performance Computers, SIAM, 1998
• J. J. Dongarra et al.: Sourcebook of Parallel Computing, Morgan Kaufmann, 2003
• V. Eijkhout: Introduction to High Performance Scientific Computing, lulu.com, 2011
• M. J. Gander: Optimized Schwarz Methods. SIAM Journal on Numerical Analysis, 2006, 44(2):699-731
• J. Kruis: Domain Decomposition Methods for Distributed Computing, Saxe-Coburg, 2006
• V. Kumar, A. Grama, A. Gupta, G. Karypis: Introduction to Parallel Computing, Benjamin/Cummings, 1994
• F. Magoulès (ed.): Substructuring Techniques and Domain Decomposition Methods, Saxe-Coburg, 2010
• A. Quarteroni, A. Valli: Domain Decomposition Methods for Partial Differential Equations, Oxford Univ. Press, 1999
• L. R. Scott, D. Xie: Parallel Linear Stationary Iterative Methods, in P. Bjørstad, M. Luskin (eds): Parallel Solution of Partial Differential Equations. Springer, 2000
• B. F. Smith, P. E. Bjørstad, W. Gropp: Domain Decomposition, Cambridge Univ. Press, 2004
• T. Rauber, G. Rünger: Parallele und verteilte Programmierung, Springer, 2000
• A. Toselli, O. B. Widlund: Domain Decomposition Methods, Springer, 2005
• U. Trottenberg, C. W. Oosterlee, A. Schüller: Multigrid, Elsevier Acad. Press, 2007
• J. Xu: Iterative Methods by Space Decomposition and Subspace Correction, SIAM Review, 1992, 34(4):581-613

Supplementally: Finite Element Method

• D. Braess: Finite Elemente - Theorie, schnelle Löser und Anwendungen in der Elastizitätstheorie, 4. überarb. und erw. Aufl., Springer, 2007
• S. C. Brenner, L. R. Scott: The Mathematical Theory of Finite Element Methods, 3. ed., Springer, 2008
• P. G. Ciarlet: The Finite Element Method for Elliptic Problems, Reprint by SIAM, 2002
• A. Ern, J.-L. Guermond: Theory and Practice of Finite Elements, Springer, 2004

Supplementally: Iterative Solvers

• W. Hackbusch: Iterative Solution of Large Sparse Systems of Equations. Springer, 1994.

Supplementally: Functional Analysis and PDEs

• H. W. Alt: Lineare Funktionalanalysis, 6. Aufl., Springer, 2012
• L. C. Evans: Partial Differential Equations, 2. ed., AMS, 2010
• G. Leoni: A First Course in Sobolev Spaces, AMS, 2009