Geometric multigrid methods solve an elliptic boundary value problem on a sequence of grids generated by a refinement procedure.  They have optimal complexity in the sense that the computational cost is proportional to the number of unknowns.  In this tutorial we will introduce various multigrid algorithms (V-cycle, W-cycle, F-cycle, etc.) and discuss their convergence analysis.

Multigrid methods are so-called optimal methods because they can solve a system of N unknowns with O(N) work. This optimality property is crucial for scaling up to huge high-resolution simulations on parallel computers. To achieve this, the multigrid components must be designed with the underlying system in mind, traditionally, the problem geometry. Algebraic multigrid, however, is a method for solving linear systems using multigrid principles, but requiring no explicit geometric information. Instead, AMG determines the essential multigrid ingredients based solely on the matrix entries. Since the method's introduction in the mid-eighties, researchers have developed numerous AMG algorithms with different robustness and efficiency properties that target a variety of problem classes. In this tutorial, we will introduce the AMG method, beginning with a description of the classical algorithm of Achi Brandt, Steve McCormick, John Ruge, and Klaus Stüben, and then move on to more recent advances and theoretical developments.

Domain decomposition, a form of divide-and-conquer for mathematical problems posed over a physical domain is the most common paradigm for large-scale simulation on massively parallel, distributed, hierarchical memory computers. In domain decomposition, a large problem is reduced to a collection of smaller problems, each of which is easier to solve computationally than the undecomposed problem, and most or all of which can be solved independently and concurrently. Domain decomposition has proved to be an ideal paradigm not only for execution on advanced architecture computers, but also for the development of reusable, portable software. The most complex operation in a typical domain decomposition method – the application of the preconditioner – carries out in each subdomain steps nearly identical to those required to apply a conventional preconditioner to the undecomposed domain. Hence software developed for the global problem can readily be adapted to the local problem, instantly presenting lots of legacy scientific code for to be harvested for parallel implementations. Finally, it should be noted that domain decomposition is often a natural paradigm for the modeling community. Physical systems are often decomposed into two or more contiguous subdomains based on phenomenological considerations, and the subdomains are discretized accordingly, as independent tasks. This physically-based domain decomposition may be mirrored in the software engineering of the corresponding code, and leads to threads of execution that operate on contiguous subdomain blocks. This tutorial provides an overview of domain decomposition and focuses on the mathematical development of its two main paradigms: Schwarz and Schur preconditioning and their hybrids.

Adaptivity is an essential tool in modern scientific and engineering computation that allows one to optimize the computational effort by locating the degrees of freedom where they are most needed, that is in regions of rapid solution variation. Adaptive finite element methods (AFEM) are the most popular and effective numerical methods to solve elliptic PDE, and are driven by a posteriori error estimators. In this tutorial we will discuss the basic structure of AFEM and its main properties, analyze its convergence (contraction property), and derive convergence rates.

Variational formulation and piece-wise linear finite element approximations of Poisson's problem. Dirichlet and Neumann boundary conditions and Poincaré's and Friedrichs's inequalities. A word about linear elasticity. Condition numbers of finite element matrices and the preconditioned conjugate gradient method.

Domains and subdomains. Subdomain matrices as building blocks for domain decomposition methods and the related Schur complements. The two-subdomain case: the Neumann--Dirichlet and Schwarz alternating algorithms; they can be placed in a unified framework and written in terms of Schur complements. Extension to the case of many subdomains; coloring, the problems of singular subdomain matrices, and the need to use a coarse, global problem. Three assumptions and the basic result on the condition number of additive Schwarz algorithms.

Classical and more recent two--level additive Schwarz methods. Remarks on the effect of irregular subdomains. Extensions to elasticity problems including the almost incompressible case.

Modern iterative substructuring methods: FETI–DP and BDDC. An introduction in terms of block-Cholesky for problems only partially assembled. The equivalence of the spectra. Results on elasticity including incompressible Stokes problems.

This tutorial will provide an overview of the concepts of parallel computing. Topics to be discussed comprise parallel programming models and computer architectures, including multicore architectures, as well as various issues that need to be considered when designing parallel programs. Several examples of parallel solvers will be presented to illustrate the challenges that need to be overcome to achieve an efficient implementation.