Parallel Multigrid in an Adaptive PDE Solver Based on Hashing

INTRODUCTION We consider partial differential equations, e.g. an elliptic scalar differential equation on a two-dimensional domain. For reasons of efficiency, we use an optimal order solution algorithm: The dicretized equation system is solved by a multigrid method. In order to accelerate the solution procedure further, adaptivity is employed to achieve a given error tolerance with less unknowns. The grid is adapted to the solution and is refined only in regions of the domain where necessary. A third way to speed up the computation is parallel computing. We partition the data and distribute it to several processors and we assign the operations on that data preferably to the processor who owns the data. We intend to put all three methods (multigrid, adaptivity, parallelism) efficiently together. This requires some additional considerations. While state-of-the-art computer codes use tree data structures to implement such a method, we will propose hash tables instead. Hash tabl