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.
matrix partitioning, iterative method, parallel computing, rectangular matrix, structurally unsymmetric matrix, bipartite graph
@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},
}