Parallel multilevel tetrahedral grid refinement

Abstract. In this paper we analyze a parallel version of a multilevel red/green local refinement algorithm for tetrahedral meshes. The refinement method is similar to the approaches used in the UG-package [33] and by Bey [11, 12]. We introduce a new data distribution format that is very suitable for the parallel multilevel refinement algorithm. This format is called an admissible hierarchical decomposition. We will prove that the application of the parallel refinement algorithm to an input admissible hierarchical decomposition yields an admissible hierarchical decomposition. The analysis shows that the data partitioning between the processors is such that we have a favourable data locality (e.g., parent and children are on the same processor) and at the same time only a small amount of copies. AMS subject classifications. 65N50, 65N5