Bilkent University
Department of Computer Engineering
S E M I N A R
Combinatorial Reductions Between Graph Partitioning by Vertex Separator and Hypergraph Partitioning Problems For Parallel and Scientific Computing
Enver Kayaaslan
MSc. Student
Computer Engineering Department
Bilkent University
Hypergraph Partitioning (HP) and Graph Partitioning by Vertex Separator (GPVS) problems are very well known problems which are used in scientific and parallel computing effectively. A typical problem in parallel computing is to partition the datas/tasks into several processors such that the overall performance of the computation gets more qualified in terms of time and/or memory. Besides GPVS is generally used for fill-reducing ordering of sparse matrices for solving sparse linear systems efficiently which lies into the area of scientific computing. In this thesis, the relation between these two problems are investigated. Two combinatorial reductions, from HP Problem to GPVS Problem and from GPVS Problem to HP Problem are disclosed along with their theoritical bases. In practice, the untrivial part of HP Problem to GPVS Problem reduction is the input transformation, that is, converting a graph to a hypergraph such that the reduction holds. The untrivial part of the reduction from GPVS Problem to HP Problem is the output transformation, that is, decoding a vertex separator of the corresponding graph to a partition for the hypergraph. These untrivial parts are investigated deeply and effective and efficient algorithms and methods are proposed. To validate the effectiveness and/or efficiency of the algorithms and methods, one application for each reduction is experimented. An HP-based ordering tool based on PaToH is enhanced along with implemantation of input transformations and presented as a package called oPaToH. A GPVS-based HP tool is constructed from MeTiS along with output transformations, which is called HPMeTiS as a package. The fill-reducing ordering results obtained with oPaToH produced more quialified ordering results such as up to %20 improvements for operation count compared to state-of-the art ordering tools such as onMeTiS. The hypergraph partitioning results with HPMeTiS produced results around 2 times faster than the state-of-the art hypergraph partitioning tool PaToH with comparable quality for net balancing.
DATE: 20 August, 2009, Thursday @ 13:30
PLACE: EA 409