A Geometry-aware Data Partitioning Algorithm for Parallel Quad Mesh Generation on Large-scale 2D Regions

详细信息    查看全文

• 作者：Wuyi Yu ; Xin Li ; ^{xinli@lsu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Geometry-aware Data Partitioning ; Parallel Mesh Generation ; Large-scale Structural Meshing
• 刊名：Procedia Engineering
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：124
• 期：Complete
• 页码：44-56
• 全文大小：1535 K

文摘

We develop 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 as a quadratic integer optimization problem with linear constraints. Directly solving this problem is expensive 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 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 quadrilateral mesh generation. We demonstrate that our decomposition algorithm outperforms existing approaches by offering a higher-quality partitioning, and therefore, improved performance and quality in mesh generation.