Parallel partitioning tool for large mesh decomposition

Problem of balanced distribution of mesh among processors arises in numerical solution on distributed memory systems of problems in computational fluid dynamics and computational mechanics. Parallel decomposition of triangular and tetrahedral meshes, containing up to $10^9$ vertices, is the aim of this research. Methods, realized in state-of-the-art parallel partitioning tools PARMETIS, JOSTLE, PT-SCOTCH and ZOLTAN, are based on multilevel algorithms that have a shortcoming of formation of unconnected domains. Second shortcoming of the most often used package PARMETIS is generation of strongly unbalanced results of mesh partitioning when partitioning on great number of domains, in particular formation of domains without vertices. Parallel incremental algorithm of graph partitioning and parallel geometric algorithm of mesh partitioning are developed on basis of the incremental algorithm of graph partitioning and the recursive coordinate bisection algorithm. The aim of development of these algorithms is generation of balanced partitioning of triangular and tetrahedral meshes, containing up to $10^9$ vertices, on great number of connected domains. According to these algorithms parallel partitioning tool for large mesh decomposition is created.