An exact algorithm for sparse matrix bipartitioning
We present an exact branch-and-bound algorithm for sparse matrix bipartitioning. Rows and columns are partitioned instead of nonzeros to reduce computation time. For 85% of a test set of small matrices, an optimal bipartitioning was found. The largest matrix that was optimally bipartitioned has 129,042 nonzeros. A benchmark collection of optimal results will be made publicly available.
exact algorithm sparse matrix partitioning branch-and-bound hypergraph parallel computing sparse matrixvector multiplication