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.

The sparse matrix partitioning problem arises when minimizing communication in parallel sparse matrix–vector multiplications. Since the problem is NP-hard, heuristics are usually employed to find solutions. Here, we present a purely combinatorial branch-and-bound method for computing optimal bipartitionings of sparse matrices, in the sense that they have the lowest communication volume out of all possible bipartitionings obeying a certain load balance constraint. The method is based on a way of partitioning similar to the recently proposed medium-grain heuristic, which reduces the number of solutions to be considered in the branch-and-bound method.We applied the proposed optimal bipartitioner to find the optimal communication volume of all matrices of the University of Florida sparse matrix collection with 1000 nonzeros or less. For 85% of the matrices, an optimal bipartitioning was found within a single day of computation and for 58% even within a second. We also present optimal results for selected larger matrices, up to 129,042 nonzeros. The optimal bipartitionings and corresponding communication volumes are made publicly available in a benchmark collection.