@PhDThesis{ Zumbusch:2001*2,
author = {G. W. Zumbusch},
title = {Adaptive Parallel Multilevel Methods for Partial
Differential Equations},
school = {Universit\"at Bonn},
year = {2001},
annote = {thesis,parallel,habil},
type = {Habilitation},
abstract = {In this text we propose a space-filling curve enumeration
scheme for the load balancing problem. It is based on the
principles of self-similarity and scaling invariance. It
provides even multilevel locality, i.e. as much locality on
each scale as possible. We introduce the space-filling
curve schemes and prove some of the properties of the
partitions. The scheme is cheap, deterministic,
incremental, can be parallelised and provides acceptable
partitions. However, even more striking, it seems to be one
of the few partitioning methods where quasi-optimal
estimates can be shown. We are able to derive sharp
estimates both on the partition and on the multilevel
algorithms on the partition, which is more than is known
about competing graph partitioning load balancing methods
so far.
Furthermore, we give a survey of the three main aspects of
the efficient treatment of PDEs, that is, discretisation,
multilevel solution and parallelisation. We will treat the
main features of each of the three distinct topics and
cover the historical background and modern developments. We
demonstrate how all three ingredients can be put together
to give an adaptive and parallel multilevel approach for
the solution of PDEs. Error estimators and adaptive grid
refinement techniques for ordinary and for sparse grid
discretisations are presented. Different types of additive
and multiplicative multilevel solvers are discussed with
respect to parallel implementation and application to
adaptive refined grids. Efficiency issues are treated both
for the sequential multilevel methods and for the parallel
version by hash table storage techniques. Furthermore,
space-filling curve enumeration for parallel load balancing
and processor cache efficiency are discussed. We will apply
the method to elliptic boundary value problems.
We are able to derive estimates for the quality of the
partitions by space-filling curves and the load balancing
of the numerical algorithms on the grids. Even for adaptive
grid refinement within certain ranges we are able to prove
that the partitions are quasi-optimal, i.e. the cut sizes
of the dual graph are only a constant factor away from
optimum independent of the mesh size. Hence we obtain
asymptotic optimality of the parallel algorithms. This
seems to be remarkable in comparison to graph based
heuristics, where little is known about the quality.
Furthermore we were able to demonstrate the performance of
the method on a range of the world's largest parallel
computers, namely ASCI Blue Pacific and a prototype Cray
T3E (now presumably at NSA), which are each larger than any
non-US system. We complement this data by simulations run
on Parnass2, which was the first non-US self-made cluster
in the list of the world's largest 500 computers (TOP500).
We also demonstrate that this cluster is able to outperform
many other commercial parallel computers on a per processor
base. }
}