Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing

Abstract

A common operation in scientific computing is the multiplication of a sparse, rectangular, or structurally unsymmetric matrix and a vector. In many applications the matrix-transpose-vector product is also required. This paper addresses the efficient parallelization of these operations. We show that the problem can be expressed in terms of partitioning bipartite graphs. We then introduce several algorithms for this partitioning problem and compare their performance on a set of test matrices.

Publication
SIAM Journal on Scientific Computing
Date
Citation
B. Hendrickson, T. G. Kolda. Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing. SIAM Journal on Scientific Computing, Vol. 21, No. 6, pp. 2048-2072, 2000. https://doi.org/10.1137/S1064827598341475

Keywords

matrix partitioning, iterative method, parallel computing, rectangular matrix, structurally unsymmetric matrix, bipartite graph

BibTeX

@article{HeKo00a,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {21}, 
number = {6}, 
pages = {2048--2072}, 
month = {May}, 
year = {2000},
doi = {10.1137/S1064827598341475},
}