SC15 Austin, TX

Geometric-Aware Partitioning on Large-Scale Data for Parallel Quad Meshing


Authors: Wuyi Yu (Louisiana State University), Qin Chen (Louisiana State University), Jian Tao (Louisiana State University), Xin Li (Louisiana State University)

Abstract: We present a partitioning algorithm to decompose complex 2D data into small simple subregions for effective parallel quad meshing. We formulate the partitioning problem for effective parallel quad meshing, which leads to an expensive quadratic integer optimization problem with linear constraints. Directly solving this problem is prohibitive for large-scale data partitioning. Hence, we suggest a more efficient two-step algorithm to obtain an approximate solution. First, we partition the region into a set of square-like cells using L_infity Centroidal Voronoi Tessellation (CVT), then we solve a graph partitioning on the dual graph of this CVT to minimize the total boundary length of the partitioning, while enforcing the load balancing and each subregion’s connectivity. With this geometry-aware decomposition, subregions are distributed to multiple processors for parallel quadrilateral mesh generation.

Poster: pdf
Two-page extended abstract: pdf


Poster Index