Sathe, Madan. Parallel graph algorithms for finding weighted matchings and subgraphs in computational science. 2012, PhD Thesis, University of Basel, Faculty of Science.
Official URL: http://edoc.unibas.ch/diss/DissB_10076
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.
|Committee Members:||Schenk, Olaf and Bisseling, Rob|
|Faculties and Departments:||05 Faculty of Science > Departement Mathematik und Informatik > Informatik > High Performance and Web Computing (Burkhart)|
|Bibsysno:||Link to catalogue|
|Number of Pages:||200 S.|
|Last Modified:||30 Jun 2016 10:50|
|Deposited On:||08 Oct 2012 13:57|
Repository Staff Only: item control page