Partitioning sparse rectangular matrices for parallel computations of Ax and A ^T v

Abstract

This paper addresses the problem of partitioning the nonzeros of sparse nonsymmetric and nonsquare matrices in order to efficiently compute parallel matrix-vector and matrix-transpose-vector multiplies. Our goal is to balance the work per processor while keeping communications costs low. Although the symmetric partitioning problem has been well-studied, the nonsymmetric and rectangular cases have received scant attention. We show that this problem can be described as a partitioning problem on a bipartite graph. We then describe how to use (modified) multilevel methods to partition these graphs and how to implement the matrix multiplies in parallel to take advantage of the partitioning. Finally, we compare various multilevel and other partitioning strategies on matrices from different applications. The multilevel methods are shown to be best.

This work was supported by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy, under contracts DE-AC05-96OR22464 and DE-AL04-94AL85000 with Lockheed Martin Energy Research Corporation.