Mesh refinement for parallel-adaptive FEM : theory and implementation

Abstract

We investigate parallel adaptive grid refinement and focus in particular on hierarchically adaptive, parallel and conforming simplicial grids that use Newest Vertex Bisection (NVB) as their refinement strategy. One challenge of NVB is its applicability to arbitrary simplex grids, which is not possible with the current compatibility condition. We define a novel, more natural weak compatibility condition for the initial grid and show that using this condition the iterative refinement algorithm terminates using NVB. We design an algorithm to relabel an arbitrary d-dimensional simplicial grid to fulfil this weak compatibility condition. The algorithm is of complexity O(n), where n is the number of elements in the grid. We also consider NVB on partitioned grids for parallel computing. Another challenge is that refinement may propagate over partition boundaries. This is resolved by adding an outer loop to the refinement algorithm, that requires global communication. We prove that the amount of global communication needed and the number of outer iterations in the refinement propagation to reach a conforming situation is bounded. We extend the grid manager DUNE-ALUGrid to provide parallel, adaptive, conforming 2d grids. Furthermore we develop the software package DUNE-ACFem which is able to conveniently describe mathematical problems within efficient C++ code. We demonstrate the utility of DUNE-ACFEM and DUNE-ALUGrid at the problem of noise removal on images with adaptive finite elements.