Adaptive Multigrid using Finite Element Methods

Linda Stals

Universität Augsburg, Institut für Mathematik Universitätsstrasse 14, D-86159, Augsburg, Germany

Early experiments with parallel multigrid used uniform grids on square domains. More recently, several authors have written programs which handle more complicated domains by viewing the region as a (complex) composition of structured grids. The program we would like to present uses unstructured grids and can therefore solve problems on more general polygonal regions and use adaptive refinement methods. Furthermore, the data structure has been set up so that all of the work is done on the processors. That is, once the initial coarse grid is passed down from the host machine, the refinement, the multigrid solution and the load balancing are all computed in parallel thus offering a flexible high performance algorithm.

Our program uses a node-edge data structure similar to the one described by Rüde. We have implemented the data structure in parallel by dividing the nodes up into ghost nodes and full nodes. The full nodes sit in the interior of the processors while the ghost nodes sit on the boundary and are a generalisation of the processor boundary layer or artificial boundary used in structured grids. The ghost nodes are also used to complete the inter-grid connections (i.e. interpolation and restriction operators) thus allowing the individual grid levels to be spread separately across the processors.

The grids are refined by using the newest node bisection method. We have found that this method works well with our parallel data structure. For example, during refinement the communication pattern has to be updated when new nodes are added and by exploiting the relationship between ghost nodes and full nodes it is updated independently across the processors.

To handle adaptive refinement in parallel we have extended the newest node bisection method by introducing interface-base edges. Interface-base edges are edges which sit between two different levels of refinement and control the order of refinement to ensure that the angles remain bound away from 0 and π.

If we allow adaptive refinement we need to address the problem of load balancing. The load is balanced by using a four step method. The first step finds how many nodes should be moved. The next step picks which nodes are to be moved and the third step uses the Kernighan-Lin method to determine where they should be moved to. The final step moves the nodes.

The program is written in a mixture of C^{++} and PVM. It was originally developed on a network of workstations and then moved to the AP1000 for performance testing. The AP1000 is an experimental MIMD machine from Fujitsu which contains 128 processors arranged in a 2D torus.