×

Parallel Delaunay triangulation for particle finite element methods. (English) Zbl 1156.65017

Summary: Delaunay triangulation is a geometric problem that is relatively difficult to parallelize. Parallel algorithms are usually characterized by considerable interprocessor communication or important serialized parts. We propose a method that achieves high speed-ups, but needs information regarding locally maximum element circumspheres prior to the beginning of the algorithm. Such information is directly available in iterative methods, like the particle finite element methods. The developed parallel Delaunay triangulation method has minimum communication requirements, is quite simple, and achieves high parallel efficiency.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y05 Parallel numerical computation
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs

Software:

DeWall
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Idelsohn, The particle finite element method: a powerful tool to solve incompressible flows with free-surfaces and breaking waves, International Journal for Numerical Methods in Engineering 61 pp 964– (2004) · Zbl 1075.76576
[2] Idelsohn, Fluid-structure interaction using the particle finite element method, Computer Methods in Applied Mechanics and Engineering (2005)
[3] Aggarwal, Parallel computational geometry, Algorithmica 3 pp 293– (1988) · Zbl 0664.68041
[4] Cignoni, Parallel 3D Delaunay triangulation, Computer Graphics Forum 12 pp 129– (1993)
[5] Hardwick JC Implementation sand evaluation of an efficient parallel Delaunay triangulation algorithm 1997
[6] Chen MB Chuang TR Wu JJ Efficient parallel implementations of 2D Delaunay triangulation with high performance Fortran 2001
[7] Lee, An improved parallel algorithm for Delaunay triangulation on distributed memory parallel computers, Parallel Processing Letters 11 pp 341– (2001)
[8] Chrisochoides N Sukup F Task parallel implementation of the Bowyer-Watson algorithm 1996
[9] Chrisochoides N Nave D Simultaneous mesh generation and partitioning for Delaunay meshes 1999
[10] Okusanya, 3D parallel unstructured mesh generation, Trends in Unstructured Mesh Generation AMD-220 pp 109– (1997)
[11] Kohout, Parallel Delaunay triangulation in E2 and E3 for computers with shared memory, Parallel Computing 31 pp 491– (2005)
[12] Edelsbrunner, Three-dimensional alpha-shape, ACM Transactions on Graphics 3 pp 43– (1994) · Zbl 0806.68107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.