Geometry-aware partitioning of complex domains for parallel quad meshing. (April 2017) - Li, Xin; Yu, Wuyi; Liu, Celong
Abstract: We develop a partitioning algorithm to decompose complex 2D data into small and simple subregions suitable for effective distributed and parallel quadrilateral mesh generation. To support high-quality quad mesh generation, the partitioning reduces to solving an integer quadratic optimization problem with linear constraints. Directly solving this problem is expensive for large-scale data. Hence, we also suggest a more efficient two-step algorithm to obtain an approximate solution. First, we partition the region into a set of cells using L ∞ Centroidal Voronoi Tessellation (CVT), then we solve a graph partitioning on the dual graph of this CVT to minimize the total partitioning boundary length, while enforcing the load balancing and each subregion's connectivity. With this decomposition, subregions are distributed to multiple processors for parallel mesh generation. Through comparisons on the quality of the final meshes and the performance of simulations run on these meshes, we show that our decomposition algorithm outperforms existing partitioning approaches by offering more simulation-friendly regular meshes. Highlights: A new data partitioning algorithm for large-scale quad mesh generation. A parallel computing framework for distributed geometric processing and meshing. A quad mesh generator for efficient scientific simulations of large geometric data.