On the Efficient Implementation of Adaptive Multigrid Methods

Ulrich Rüde

Institut für Mathematik, Universität Augsburg, D-86135 Augsburg, Germany


Abstract

Practical PDE problems often show increased activity in subdomains and thus an adaptive mesh generation can drastically reduce the number of unknowns in the discretized system. Modern adaptive multilevel methods are thus often based on hierarchically nested, unstructured finite element meshes. Unfortunately, the data structures required to implement these algorithms lead to a high overhead on many advanced computer architectures. The two main sources of this performance degradation are the effects of non-uniform data access combined with indirect addressing that prohibits the use of instruction-level parallelism essential in many modern CPUs. The second, and possibly more fundamental question arises from hierarchical memory architectures with several layers of caches that require programs with data access locality. These problems are addressed in the patch-adaptive multigrid method (PAM), a recently developed experimental software system implementing an adaptive multigrid method based on a locally uniform mesh data structure. The advantages of the approach are shown by performance comparisons with conventional unstructured mesh multigrid systems.

Ulrich Rüde