# 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.

Type
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},
}