Adaptive Grid Conference Edinburgh 96: chrisochoides Abstract

	Abstracts for the Conference on Grid Adaptivity in Computational PDEs, Edinburgh, July 96	Next
		Previous
		Index

Parallel adaptive Delaunay grid generation

N Chrisochoides & P Chew

Advanced Computing Research Institute
Theory Center, Cornell University
Ithaca, New York 14853-3801

Abstract

Delaunay triangulation algorithms have been used very successfully for unstructured adaptive grid generation on sequential machines. Delaunay-based algorithms generate unstructured grids by sequentially adding new points and modifying the existing triangulation by means of purely local operations. These algorithms can be viewed as iterative procedures; each iteration performs three basic operations: (i) point creation, where a new point is created using an appropriate spatial distribution technique; (ii) point location, where a triangle that contains the new point is identified; and (ii) element creation, where existing triangles which violate the circumcircle property are removed and new triangles are built by properly connecting the newly created point with old points, so that the resulting triangulation satisfies certain geometric properties [1]. The efficient implementation of Delaunay-based grid generators, on both distributed and shared memory multicomputers, requires: (i) the minimization of communication cost required by the point location operations and (ii) minimization of communication and synchronization costs required by the element creation operations.

In this paper we propose two parallel algorithms that minimize the communication required for the point location, without compromising the grid quality. Methods for the efficient implementation of the element creation step on distributed memory multicomputers are presented by Chrisochoides et. al elsewhere [2].

The first algorithm is based on earlier work of Chew [3]. Chew's technique calls for ``bad'' triangles - those that are too large or those that have an angle that is too small - to be improved by adding the triangle's circumcenter as a new grid point. We refer to this technique as the circumcenter method. It is possible to show that this strategy, in combination with some other techniques for handling the boundaries, leads to grids in which all triangles have angles between 30 and 120 degrees, except for those angles required by small angles along the specified boundary. Usually Delaunay triangulation algorithms require a search to find a triangle whose circumcenter contains a new point, but the circumcenter method requires no such search since each point is created as a circumcenter of a triangle; thus when a point is created, we already have a triangle whose circumcircle contains the point. The use of the circumcenter method minimizes the interprocess communication in the point location step. Moreover the circumcenter method can be used to uncouple the computation into two independent classes of tasks that can be executed concurrently and thus it can be used to hide some of the remaining communication.

The second algorithm is essentially a combination of the circumcenter method and the constrained Delaunay triangulation (CDT). The CDT method minimizes communication for point location operations even further and eliminates synchronization for element creation operations. Intuitively, the constrained Delaunay triangulation is as close as one can get to the Delaunay triangulation given that one is stuck with certain edges. This idea can be made mathematically precise (see for instance [4]), leading to Delaunay-based grid generators that allow internal boundaries. It is possible to show that these internal boundaries do not affect the quality of the resulting grid, although an observant user might infer the presence of such boundaries in the resulting grid by noting the way in which triangle edges are aligned. Using the idea of a CDT, we can introduce artificial boundaries into the region to be meshed, creating one subregion for each processor. Note that, by the definition of the CDT, points on one side of a boundary have no effect on triangles on the other side of the boundary; thus, no synchronization is required during the element creation process. In addition, interprocess communciation is tremendously simplified: the only message between adjacent processes is of the form, ``I have split this boundary.'' Since boundaries are always split exactly in half, no additional information needs to be communicated.

Finally, in this paper we evaluate the performance of two algorithms for unstructured adaptive grid generation on multicomputers: (i) using the circumcenter method and (ii) using both the circumcenter and CDT methods. Also, we develop and analyze methods for creating the artificial boundary so that creation of the subregions is efficient and avoids the creation of new small angles.

[1] Preparata, F. and M. Shamos, Computational Geometry, An Introduction, Springer-Verlag, pp 398, 1985.

[2] N.P. Chrisochoides and F. Sukup, Task Parallel implementation of the BOWYER-WATSON algorithm, to appear in Proceedings of Fifth International Conference on Numerical Grid Generation in Computational Fluid Dynamics and Related Fields, 1996.

[3] L. Paul Chew, Guaranteed-Quality Mesh Generation for Curved Surfaces, Proceedings of the Ninth Symposium on Computational Geometry / (1993), ACM Press, 274-280.

[4] L.Paul Chew, Constrained Delaunay Triangulations,'' Algorithmica, 4 (1989), 97-108.

	ABSTRACTS
	Next	Previous	Index

Last modified Fri Jun 21 19:19:11 GB-Eire 1996 (DBD)