Effects of quadratic programming based graph partitioning on the convergence of the block Cimmino algorithm

The Block Cimmino algorithm is successfully used for parallel solution of large systems due to its amenability of parallelism. We examine the parallel solution of large systems of sparse linear equations with the Block Cimmino algorithm. Since the convergence rate in the Block Cimmino algorithm depends on the orthogonality between the block rows created by the graph partitioning method, we propose a new partitioning method to improve this convergence rate in this thesis that a quadratic programming-based partitioning method for Block Cimmino. Our method is an recursive bisection process using the Mongoose partitioning tool. In addition, we compared the iteration numbers and total times as a result of the partitioning process using the recursive bisection algorithm that we wrote with the Mongoose library and the partitioning process performed with the GRIP method using the METIS library. Finally, through various experiments we performed on many matrices, we were able to confirm that our proposed method is valid.