The sparse matrix partitioning problem arises in parallel sparse matrix-vector multiplications, where one needs to distribute work evenly between the available processors while minimizing the amount of needed communication between processors. Given a sparse matrix A, we aim to find a partitioning of the matrix nonzeros, such that each part contains at most a certain number of nonzeros, and the number of different parts that own nonzeros in each row and column is minimized. The problem can be written as a hypergraph partitioning problem, and is NP-hard to solve. Therefore, in practice, several heuristic methods are used to find good solutions for specific instances. One-dimensional heuristic solvers partition the sparse matrix only in the row or column direction and are computationally efficient, but typically produce sub-optimal results. On the other hand, two-dimensional heuristic solvers produce better results, but can be prohibitively slow in practice.

In this talk, I will present work of Rob H. Bisseling and me on two methods for solving the sparse matrix partitioning problem. The first method is a heuristic solver [1], based on translating the sparse matrix A to a different sparse matrix B with a specific structure. This structure allows us to obtain very good results by partitioning B with a fast one-dimensional heuristic and translating the resulting partitioning of B to a partitioning of A. The method produces two-dimensional partitionings of A, while retaining the computational efficiency of standard one-dimensional heuristic solvers. This method, called the medium-grain method, is now the default in the Mondriaan sparse matrix partitioning package [2]. The second method is an exact solver [3], i.e. one that finds the optimal partitioning for a given matrix. Since the problem is NP-hard, we accept much longer computation times for an exact solver, and limit the size of the problems we expect to solve. However, analyzing optimal partitionings of sparse matrices might help improve current heuristics. The exact method is based on a branch-and-bound framework, with several lower bounds for partial solutions. We show that the exact method is able to find the optimal solution for the majority of small test matrices, and even for a few larger matrices with special structures. This method will soon become available as the tool MondriaanOpt within the Mondriaan package.

References:
[1] Pelt, D.M.; Bisseling, R.H., "A Medium-Grain Method for Fast 2D Bipartitioning of Sparse Matrices," IEEE 28th International Parallel and Distributed Processing Symposium 2014, pp.529-539, 19-23 May 2014
[2] http://www.staff.science.uu.nl/~bisse101/Mondriaan/
[3] Pelt, D.M.; Bisseling, R.H., "An exact algorithm for sparse matrix bipartitioning," Submitted for publication.