Simultaneous mesh generation and partitioning for Delaunay meshes

Nikos Chrisochoides and Démian Nave

Mathematics and Computers in Simulation (MATCOM), 2000, vol. 54, issue 4, 321-339

Abstract: In this paper, we present a new approach for the parallel generation and partitioning of unstructured 3D Delaunay meshes. The new approach couples the mesh generation and partitioning problems into a single optimization problem. Traditionally, these two problems are solved separately, first generating the mesh (usually sequentially) and then partitioning the mesh, either sequentially or in parallel. In the traditional approach, the overheads due to I/O and data movement exceed 50% of the total execution time. Even if parallel partitioning schemes are employed, data movement, synchronization, and data structure translation overheads are high; for applications which require frequent remeshing (e.g. crack growth simulations), these overheads are prohibitive. We present a method for solving the mesh partitioning and placement problem simultaneously with the mesh generation problem. By eliminating unnecessary and redundant cache, local, and remote memory accesses, we can speed up the generation and redistribution process, for very large meshes, by almost an order of magnitude compared to traditional approaches. Our results show that we can achieve nearly perfect equi-distribution of mesh elements over the processors, while maintaining reasonably good separator size, all while improving the quality of the mesh by eliminating many of the problems inherent in traditional parallel constrained mesh generation.

Keywords: Quality mesh generation; Mesh partitioning; Delaunay triangulation; Parallel computing (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475400001920
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:54:y:2000:i:4:p:321-339

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().