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.
PDF and postscript files are preprints.
@inproceedings{HeKo98,
author = {Bruce Hendrickson and Tamara G. Kolda},
title = {Partitioning Sparse Rectangular Matrices for Parallel Computations of $Ax$ and $A^Tv$},
booktitle = {Applied Parallel Computing Large Scale Scientific and Industrial Problems},
eventtitle = {4th International Workshop, PARA'98},
venue = {Ume\r{a}, Sweden},
eventdate = {1998-06-14/1998-06-17},
editor = {B. K\r{a}gstr\"{o}m and others},
series = {Lecture Notes in Computer Science},
volume = {1541},
number = {1541},
publisher = {Springer Berlin Heidelberg},
pages = {239-247},
year = {1998},
doi = {10.1007/BFb0095342},
}