The Hierarchical Basis Approach to Multilevel Adaptive Methods and Partitioning Adaptive Grids

Dr. William F. Mitchell

For many computer models of physical phenomena, the most computationally intense part of the calculation is the numerical solution of elliptic partial differential equations (PDEs). For this reason, much research has been performed to find faster methods to solve PDEs at higher resolution. Some of the improvements are: 1) high order methods, which give better accuracy relative to the number of grid points, 2) adaptive grid refinement, which decreases the number of grid points by providing higher resolution only where it is needed, 3) multi-level (multigrid) linear system solution techniques, which have the smallest possible asymptotic operation counts, and 4) high performance computer architectures, such as massively parallel computers which use hundreds or thousands of processors to solve the equation. It has recently been discovered that indirect use of a hierarchical basis for finite element methods can provide an elegant multigrid method. The hierarchical basis can also provide an elegant approach to adaptive refinement. In this talk, we will discuss adaptive refinement and multigrid from the viewpoint of hierarchical bases, and present a hierarchical multilevel adaptive method applicable to high order finite elements. The implementation of multilevel adaptive methods on parallel computers is very difficult, due to the irregularities in the data and computation. In particular, the irregular, dynamically changing, adaptive grid must be distributed over the processors with a balanced partition. We present a set of requirements that a partitioning algorithm for multilevel adaptive methods should satisfy, and a new partitioning algorithm that satisfies most of these requirements.