Beyond bipartitioning: Exact sparse matrix partitioning into multiple parts.

Abstract

Matrix-vector multiplications appear in many algorithms, and in many cases the matrices used in these multiplications are sparse. The time needed for the matrix-vector multiplication computation can be decreased by performing the multiplication in parallel. In order to minimize the communication in parallel sparse matrix-vector multiplications, we need to solve the sparse matrix partitioning problem, that is the partitioning of a sparse matrix A into p disjoint parts, while minimizing the communication volume. This problem is NP-Complete. We present an algorithm based on the branch and bound method which optimally partitions a matrix into p disjoint parts, for the general case of p is greater than or equal to 2. We also present an integer linear programming model which solves the sparse matrix partitioning problem. We used the results found by these exact methods for p=4 to analyse the performance of recursive bipartitioning. The results show that the recursive bipartitioning method performs very well.