Graph partitioning for scientific computing applications
Irene Moulitsas, Yousef El-Mabruk Saad, George Karypis · 2005
Many scientific computing applications rely on efficiently partitioning the underlying graph. This thesis focuses on three areas. One of the challenges in successfully extending geometric multigrid methods to unstructured grids is generating appropriate coarse grids. We develop robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been successful in solving the related graph partitioning problem. Next, we focus on domain decomposition based numerical simulations whose subproblems are solved using sparse direct factorization methods. Effective load-balancing of such computations requires that the partitioning simultaneously balances the time required to factor the local subproblem using direct factorization, and the number of elements assigned to each processor. We develop an algorithm that follows a predictor-corrector approach that first computes a high quality partitioning of the graph, and then modifies it to achieve desired balancing constraints. During the corrector, step we compute a fill reducing ordering per partition, and then we modify the initial partitioning and ordering so that our objectives are satisfied. Existing partitioning algorithms provide limited support for load balancing simulations that are performed on heterogeneous parallel computing platforms. On such architectures, effective load balancing can only be achieved if the mesh is distributed so that it properly takes into account the available resources (CPU speed, network bandwidth). We develop a graph partitioning algorithm that can address the partitioning requirements of the scientific computations, and can correctly model the architectural characteristics of emerging hardware platforms.