Hartung-Gorre Verlag

Inh.: Dr. Renate Gorre

D-78465 Konstanz

Fon: +49 (0)7533 97227

Fax: +49 (0)7533 97228




Series in Computational Science
edited by Illia Horenka, Rolf Krause, Olaf Schenk

Volume 2


Madan Sathe

Parallel Graph Algorithms for Finding
Weighted Matchings and Subgraphs in
Computational Science

1st edition/ 1. Auflage 2012. IV, 204 pages/Seiten, € 64,00. ISBN 978-3-86628-435-7


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.



About the Author:



Madan Sathe studied computer science at the TU Dortmund University, Germany. He graduated in 2007 with a diploma thesis in the field of multiobjective optimization in collaboration with the Indian Institute of Technology Kanpur, India. In his doctoral studies in computer science at the University of Basel, Switzerland, he worked as a research assistant in the fields of graph algorithms, scientific computing, and high-performance computing. During this time he also went on a research visit to Purdue University, USA. He was awarded a Ph.D. from the University of Basel in 2012.

Keywords: Graph Algorithms, Scientific Computing, High Performance Computing

Bookorders at / Buchbestellungen in Ihrer Buchhandlung oder direkt:

Hartung-Gorre Verlag D-78465  Konstanz // Germany

Telefon: +49 (0) 7533 97227 // Telefax: +49 (0) 7533 97228


eMail: verlag@hartung-gorre.de

Series in Computational Science