Parallel graph algorithms for finding weighted matchings and subgraphs in computational science

摘要

Graphs constitute one of the most crucial data structures in computational science and engineering. The algorithms operating on these data structures are computational kernels in various data intensive applications; for instance, in social network analysis, in computational biology, and in scientific computing. In order to enhance the computational performance of graph algorithms, techniques of high-performance computing represent the key to run these algorithms on massively parallel architectures. However, graph algorithms typically feature irregular memory access patterns and low arithmetic intensities which present a challenge for the engineering of efficient parallel graph algorithms.ududIn this thesis, a parallel auction-based weighted matching implementation, PAUL, is designed to solve the bipartite weighted graph matching problem on distributed memory clusters. This thesis outlines that the solving of graph matching problems can be significantly accelerated in various data intensive applications such as the graph similarity of protein-protein interaction networks and the permutation of large entries onto the main diagonal of a matrix in numerical linear algebra. ududFurthermore, a dense subgraph problem is identified in parallel numerical linear algebra whose solution considerably improves the convergence and robustness of hybrid linear solvers. Three heuristics are designed and implemented to solve the NP-hard combinatorial problem efficiently; the most promising one is based on evolutionary algorithms. The impact of solving the heuristics is demonstrated in the hybrid linear solver PSPIKE when solving data intensive applications in arterial fluid dynamics and PDE-constrained optimization.ud