A&S Departments and Programs   • Graduate Study Offered   American Studies • Anthropology • Applied Science • Art & Art History Biology • Black Studies Chemistry • Classical Studies Computer Science • Economics English Environmental Science & Policy Film Studies Geology Global Studies Government History • International Relations Kinesiology Linguistics Literary & Cultural Studies Mathematics Medieval & Renaissance Studies Military Science Modern Languages Music Neuroscience Philosophy Physics • Psychology • Public Policy • Religious Studies Sociology Theater, Speech & Dance Women's Studies

Search

Find People

Computer Science Department

Computer Science Department

Decoupling Method for Parallel Delaunay 2D Mesh Generation

Leonidas Linardakis
June 14, 10:00 AM
McGlothlin-Street Hall 002

Abstract

Meshes are central structures for numerical methods, such as the finite element method. These numerical methods require high quality refined meshes, in order to guarantee good approximations of the analytical model. Unstructured meshes are the most popular; their adaptive nature allows them to give boundary conforming meshes of good quality, with optimal size. The most widely studied 2D mesh generation method is the Delaunay method.

Creating in parallel guaranteed quality large unstructured meshes is a challenging problem. The Delaunay refinement procedure is memory intensive with unpredictable computational behavior. Moreover, geometries may be quite complex, adding difficulty to parallelize the mesh generation. Parallel mesh generation procedures decompose the original mesh generation problem into smaller subproblems that can be solved in parallel. The subproblems can be treated as either completely or partially coupled, or they can be treated as completely decoupled.

Parallel mesh generation procedures that are based on geometric domain decompositions require the permanent separators to be of good quality (in terms of their angles and length), in order to maintain the mesh quality. The Medial Axis domain decomposition, an innovative geometric domain decomposition procedure that addresses this problem, is introduced. The Medial Axis domain decomposition is of high quality in terms of the formed angles, and provides separators of small size, and also good work-load balance. It presents for the first time a decomposition method suitable for parallel meshing procedures that are based on geometric domain decompositions.

The decoupling method for parallel Delaunay 2D mesh generation is a highly efficient and effective parallel procedure, able to generate billions of elements in a few hundred of seconds, on distributed memory machines. Our mathematical formulation introduces the notion of the decoupling path, which guarantees the decoupling property, and also the quality and conformity of the Delaunay submeshes. The subdomains are meshed independently, and as a result, the method eliminates the communication and the synchronization during the parallel meshing. A method for shielding small angles is introduced, so that the decoupled parallel Delaunay algorithm can be applied on domains with small angles. Moreover, we present the construction of a sizing function, that encompasses an existing sizing function, and also geometric features and small angles. The decoupling procedure can be used for parallel graded Delaunay mesh generation, controlled by the sizing function.

The decoupling approach allows 100% code re-use of existing, fine-tuned and well tested, sequential mesh generators, minimizing the effort of code parallelization. Our results indicate high scalability of the decoupling approach, and also show superlinear speed-ups, when compared to the sequential library.