Paralel ve bilimsel hesaplama uygulamaları için hiperçizge bölümleme ve düğüm ayıracı ile çizge bölümleme problemlerinin birbirine kombinatoriyal dönüştürümü

Hypergraph Partitioning (HP) and Graph Partitioning by Vertex Separator (GPVS)problems are very well known problems which are used in scienti ? c and parallel com-puting effectively. A typical problem in parallel computing is to partition the data/tasksinto several processors such that the overall performance of the computation gets morequali ? ed in terms of time and/or memory. Besides, GPVS is generally used for ? ll-reducing ordering of sparse matrices for solving sparse linear systems ef ? ciently whichlies in the area of scienti ? c computing. In this thesis, the relation between these twoproblems, HP and GPVS problems, are investigated. Two combinatorial reductions,from HP Problem to GPVS Problem and from GPVS Problem to HP Problem are dis-closed along with their theoretical bases. In practice, the nontrivial part of HP Problemto GPVS Problem reduction is the input transformation, that is, converting a graph toa hypergraph such that the reduction holds. The nontrivial part of the reduction fromGPVS Problem to HP Problem is the output transformation, that is, decoding a vertexseparator of the corresponding graph to a partition for the hypergraph. In this part,some useful impossibility results are derived. These nontrivial parts are investigateddeeply and effective and ef ? cient algorithms and methods are proposed.Furthermore, ?oPaToH?, an HP-based ? ll-reducing ordering tool based on PaToH,is enhanced along with implementation of input transformations. Besides, based on? ll-reducing ordering tool onmetis, a GPVS-based HP tool ?hpmetis? is derived anda Dantzig-Wolfe decomposition tool for ef ? cient parallelizm of linear programmingproblem solutions is constructed, which is called as ?dwmetis?. The ? ll-reducing or-dering results obtained with enhanced oPaToH produced more quali ? ed ordering re-sults such as up to %20 improvements for operation count compared to state-of-theart ordering tools such as onmetis. Note that decreasing operation count relates toperforming sparse linear equation solutions faster. The Dantzig-Wolfe decompositionresults with dwmetis produced results around 5 times faster than the state-of-the arthypergraph partitioning tool PaToH with comparable quality for net balancing. Thisis also valuable because the preprocessing overhead is also considered inside the totalexecution time, generally. As a result, in this work it is showed that parallel and sci-enti ? c computing applications can be performed faster by exploiting the combinatorialreductions between HP problem and GPVS problem.