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

Sathe, Madan. Parallel graph algorithms for finding weighted matchings and subgraphs in computational science. 2012, Doctoral Thesis, University of Basel, Faculty of Science.


Official URL: http://edoc.unibas.ch/diss/DissB_10076

Downloads: Statistics Overview


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.
In 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.
Furthermore, 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.
Advisors:Burkhart, Helmar
Committee Members:Schenk, Olaf and Bisseling, Rob
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Ehemalige Einheiten Mathematik & Informatik > High Performance and Web Computing (Burkhart)
UniBasel Contributors:Sathe, Madan and Burkhart, Helmar and Schenk, Olaf
Item Type:Thesis
Thesis Subtype:Doctoral Thesis
Thesis no:10076
Thesis status:Complete
Number of Pages:200 S.
Identification Number:
edoc DOI:
Last Modified:22 Jan 2018 15:51
Deposited On:08 Oct 2012 13:57

Repository Staff Only: item control page