Turkish Journal of Electrical Engineering and Computer Sciences
DOI
10.55730/1300-0632.4004
Abstract
The block Cimmino method is successfully used for the parallel solution of large linear systems of equations due to its amenability to parallel processing. Since the convergence rate of block Cimmino depends on the orthogonality between the row blocks, advanced partitioning methods are used for faster convergence. In this work, we propose a new partitioning method that is superior to the state-of-the-art partitioning method, GRIP, in several ways. Firstly, our proposed method exploits the Mongoose partitioning library which can outperform the state-of-the-art methods by combining the advantages of classical combinatoric methods and continuous quadratic programming formulations. Secondly, the proposed method works on the numerical values in a floating-point format directly without converting them to integer format as in GRIP. This brings an additional advantage of obtaining higher quality partitionings via better representation of numerical values. Furthermore, the preprocessing time is also improved since there is no overhead in converting numerical values to integer format. Finally, we extend the Mongoose library, which originally partitions graphs into only two parts, by using the recursive bisection paradigm to partition graphs into more than two parts. Extensive experiments conducted on both shared and distributed memory architectures demonstrate the effectiveness of the proposed method for solving different types of real-world problems.
Keywords
Parallel computing, graph partitioning, quadratic programming, Mongoose, recursive bisection, block Cimmino.
First Page
596
Last Page
611
Recommended Citation
TAŞ, ZUHAL and TORUN, FAHREDDİN ŞÜKRÜ
(2023)
"Quadratic programming based partitioning for Block Cimmino with correct value representation,"
Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 31:
No.
3, Article 8.
https://doi.org/10.55730/1300-0632.4004
Available at:
https://journals.tubitak.gov.tr/elektrik/vol31/iss3/8
Included in
Computer Engineering Commons, Computer Sciences Commons, Electrical and Computer Engineering Commons