A Parallel Sparse Hybrid Solver and Its Relations to Graphs and Hypergraphs

In this whitepaper, we review the state-of-the-art hybrid solver, which uses generalized form DS factorization, for solving system of equations of the form Ax = f, and this solver’s relations to graphs and hypergraphs. We investigate two different reordering strategies for the DS factorization preconditioning scheme: reordering via graph partitioning (GP) and reordering via hypergraph partitioning (HP).In the GP scheme, the partitioning objective of minimizing the edge cutsize corresponds to minimizing the total number of nonzeros in the off-diagonal blocks of the reordered matrix. In the HP scheme, the partitioning objective of minimizing the cutsize, according to the cut-net metric, corresponds to minimizing the total number of nonzero columns in the off-diagonal blocks of the reordered matrix. In both of the two schemes, partitioning constraint of maintaining balance on the part weights corresponds to maintaining balance on the nonzero counts of the diagonal blocks of the reordered matrix. The partitioning objective of GP relates to minimizing the number of nonzeros in the reduced system, whereas the partitioning objective of HP exactly models minimizing the size of the reduced system. We tested the performance of two partitioning schemes on a wide range of matrices for 4-, 8-, 16-, 32-, and 64-way permutations. Results showed that HP scheme performs better than GP scheme in terms of solution times