A Template for Developing Next Generation Parallel Delaunay Refinement Methods. Andrey Chernikov and Nikos Chrisochoides. Finite Elements in Analysis and Design, in press, 2009.

Abstract

We describe a complete solution for both sequential and parallel construction of guaranteed quality Delaunay meshes for general two-dimensional geometries. We generalize the existing sequential point placement strategies for guaranteed quality mesh refinement: instead of a specific position for a new point, we derive two types of two-dimensional regions which we call selection disks. Both types of selection disks are inside the circumdisk of a poor quality triangle, with the Type I disk always inside the Type II disk. We prove that any point placement algorithm which inserts Steiner points inside selection disks of Type I terminates, and any algorithm which inserts Steiner points inside selection disks of Type II produces an asymptotically size-optimal mesh. In the area of parallel Delaunay mesh refinement, we develop a new theoretical framework for the construction of graded meshes on parallel architectures, i.e., for parallel mesh generation with element size controlled by a user-defined criterion. Our sufficient conditions of point Delaunay-independence allow to select points for concurrent insertion in such a way that the standard sequential guaranteed quality Delaunay refinement procedures can be applied in parallel to attain the required element quality constraints. Finally, we present a novel parallel algorithm which can be used in conjunction with any sequential point placement strategy that chooses points within the selection disks. We implemented our algorithm for shared memory multi-core architectures and present the experimental results. Our data show that even on workstations with a few cores, which are now in common use, our implementation is significantly faster than the best sequential counterpart.

Paper draft

pdf format pdf (2.2 M)

BibTex

@article{fead09,
    author = "Andrey Chernikov and Nikos Chrisochoides",
    title = "A Template for Developing Next Generation Parallel Delaunay Refinement Methods",
    journal = "Finite Elements in Analysis and Design",
    year = "2009",
    note = "in press",
}