Hartung-Gorre Verlag
Inh.: Dr.
Renate Gorre D-78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de
|
S
|
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
http://www.hartung-gorre.de