Leonidas Linardakis
Abstract
We present a geometric domain decomposition method and its implementation, which produces good domain decompositions in terms of three basic criteria: (1) The boundary of the subdomains create good angles, that is, angles no smaller than a given tolerance Φ0, where the value of Φ0 is determined by the application which will use the domain decomposition. (2) The size of the separator should be relatively small compared to the area of the subdomains. (3) The maximum area of the subdomains should be close to the average subdomain area. The domain decomposition method uses an approximation of a Medial Axis as an auxiliary structure for constructing the boundary of the subdomains (separators). The N-way decomposition is based on the “divide and conquer” algorithmic paradigm and on a smoothing procedure that eliminates the creation of any new artifacts in the subdomains. This approach produces well shaped uniform and graded domain decompositions, which are suitable for parallel mesh generation.
Supplemental Material
Available for Download
Software for A static geometric Medial Axis domain decomposition in 2D Euclidean space
- Attali, D., Boissonnat, J.-D., and Edelsbrunner, H. Stability and computation of the medial axis---a state-of-the-art report. In Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer-Verlag, Berlin, Germany.Google Scholar
- Barker, K., Chrisochoides, N., Chernikov, A., and Pingali, K. 2004. A load balancing framework for adaptive and asynchronous applications. IEEE Trans. Paral. Distrib. Syst. 15, 2, 183--192. Google ScholarDigital Library
- Barnard, S. T. and Simon, H. D. 1994. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurr. Pract. Exper. 6, 101--107.Google ScholarCross Ref
- Berger, M. and Bokhari, S. 1985. A partitioning strategy for pdes across multiprocessors. In Proceedings of the 1985 International Conference on Parallel Processing.Google Scholar
- Blum, H. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form. MIT Press, 362--380.Google Scholar
- Borouchaki, H., George, P. L., Hecht, F., Laug, P., and Saltel, E. 1997. Delaunay mesh generation governed by metric specifications, Part I. Algorithms and Part II. Applications. Finite Elem. Anal. Design 25, 61--83 and 85--109. Google ScholarDigital Library
- Brandt, J. W. and Algazi, V. R. 1992. Continuous skeleton computation by Voronoi diagram. Comput. Vision, Graph., Image Process. 55, 329--338. Google ScholarDigital Library
- Chernikov, A. and Chrisochoides, N. 2004. Practical and efficient point insertion scheduling method for parallel guaranteed quality Delaunay refinement. In Proceedings of the 18th Annual International Conference on Supercomputing. Malo, France, 48--57. Google ScholarDigital Library
- Chew, L. P. 1989. Guaranteed quality triangular meshes. Tech. rep. TR-89-983, Department of Computer Science, Cornell University.Google Scholar
- Chew, L. P. 1993. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of the 9th Annual Symposium on Computational Geometry. ACM, 274--280. Google ScholarDigital Library
- Chew, L. P., Chrisochoides, N., and Sukup, F. 1997. Parallel constrained Delaunay triangulation. In Proceedings of the ASME/ASCE/SES Special Symposium on Trends in Unstructured Mesh Generation. Evanston, IL, 89--96.Google Scholar
- Chrisochoides, N. 1996. Multithreaded model for the dynamic load-balancing of parallel adaptive pde computations. Appl. Numer. Math. 20, 349--365. Google ScholarDigital Library
- Chrisochoides, N. and Nave, D. 2003. Parallel Delaunay mesh generation kernel. Int. J. Numer. Meth. Engin. 58, 2, 161--176.Google ScholarCross Ref
- Deister, F., Tremel, U., Hasan, O., and Weatherill, N. P. 2004. Fully automatic and fast mesh size specification for unstructured mesh generation. Engin. Comput. 20, 237--248.Google ScholarDigital Library
- Dong, S. and Karniadakis, G. 2005. DNS of flow past a stationary and oscillating rigid cylinder at re = 10,000. J. Fluids Struct. 20, 4, 519--531.Google ScholarCross Ref
- Galtier, J. and George, P.-L. 1996. Prepartitioning as a way to mesh subdomains in parallel. In 5th International Meshing Roundtable. Pittsburgh, PA, 107--122.Google Scholar
- Hendrickson, B. and Leland, R. W. 1995a. The Chaco user's guide version 2.0. Tech. rep., Sandia National Laboratories.Google Scholar
- Hendrickson, B. and Leland, R. W. 1995b. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Scien. Comput. 16, 2, 452--469. Google ScholarDigital Library
- Hendrickson, B. and Leland, R. W. 1995c. A multi-level algorithm for partitioning graphs. In Proceedings of the ACM/IEEE Conference on Supercomputing. San Diego, CA. Google ScholarDigital Library
- Kadow, C. and Walkington, N. 2003. Design of a projection-based parallel Delaunay mesh generation and refinement algorithm. In 4th Symposium on Trends in Unstructured Mesh Generation.Google Scholar
- Karypis, G. and Kumar, V. 1995a. A fast and high quality multilevel scheme for partitioning irregular graphs. Tech. Rep. TR 95-035, Department of Computer Science, University of Minnesota, MN.Google Scholar
- Karypis, G. and Kumar, V. 1995b. MeTis: Unstructured graph partitioning and sparse matrix ordering system, version 2.0. Tech. rep., Department of Computer Science, University of Minnesota, Minneapolis, MN.Google Scholar
- Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Sys. Tech. J. 49, 2, 291--307.Google ScholarCross Ref
- Linardakis, L. and Chrisochoides, N. 2006. Delaunay Decoupling Method for parallel guaranteed quality planar mesh refinement. SIAM J. Scie. Comput. 27, 4, 1394--1423. Google ScholarDigital Library
- Löhner, R. 1997. Automatic unstructued grid generators. Finite Elem. Anal. Design 25, 111--135. Google ScholarDigital Library
- Metis. http://www-users.cs.umn.edu/~karypis/metis/index.html.Google Scholar
- mview. http://mview.sourceforge.net/.Google Scholar
- Nour-Omid, B., Raefsky, A., and Lyzenga, G. 1986. Solving finite element equations on concurrent computers. Amer. Soc. Mech. Eng, 291--307.Google Scholar
- Owen, S. J. and Saigal, S. 1997. Neighborhood-based element sizing control for finite element surface meshing. 6th International Meshing Roundtable.Google Scholar
- Ruppert, J. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algor. 18, 3, 548--585. Google ScholarDigital Library
- Said, R., Weatherill, N., Morgan, K., and Verhoeven, N. 1999. Distributed parallel Delaunay mesh generation. Comp. Methods Appl. Mech. Engin. 177, 109--125.Google ScholarCross Ref
- Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds. Lecture Notes in Computer Science, vol. 1148. Springer-Verlag, 203--222. Google ScholarDigital Library
- Showme. http://www.cs.cmu.edu/~quake/showme.html.Google Scholar
- Smith, B., Bjrstad, P., and Gropp, W. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- Triangle. http://www.cs.cmu.edu/~quake/triangle.html.Google Scholar
- Walshaw, C., Cross, M., and Everett, M. G. 1997. Parallel dynamic graph partitioning for adaptive unstructured meshes. J. Paral. Distrib. Comput. 47, 2, 102--108. Google ScholarDigital Library
- Zhu, J., Blacker, T., and Smith, R. 2002. Background overlay grid size functions. In Proceedings of the 11th International Meshing Roundtable. Sandia National Laboratories, 65--74.Google Scholar
Index Terms
- Algorithm 870: A static geometric Medial Axis domain decomposition in 2D Euclidean space
Recommendations
Algorithm 872: Parallel 2D constrained Delaunay mesh generation
Delaunay refinement is a widely used method for the construction of guaranteed quality triangular and tetrahedral meshes. We present an algorithm and a software for the parallel constrained Delaunay mesh generation in two dimensions. Our approach is ...
Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains
Special issue on the 18th annual symposium on computational geometrySoCG2002We describe a distributed memory parallel Delaunay refinement algorithm for simple polyhedral domains whose constituent bounding edges and surfaces are separated by angles between 90° to 270° inclusive. With these constraints, our algorithm can generate ...
Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains
SCG '02: Proceedings of the eighteenth annual symposium on Computational geometryWe describe a distributed memory parallel Delaunay refinement algorithm for polyhedral domains which can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, as long as the angle separating any two incident ...
Comments