November 28 - 29, 2010
Keywords of the presentation: multigrid, finite element methods
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.
Keywords of the presentation: adaptivity, finite element methods, a posteriori error estimators, contraction, decay rates
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.
Keywords of the presentation: domain decomposition, finite elements, parallel computing, overlapping Schwarz methods, BDDC and FETI–DP algoritms
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.
Keywords of the presentation: parallel computing, programming models, computer architectures, parallel solvers
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.