Partitioning Sparse Rectangular Matrices

Tamara G. Kolda 
Oak Ridge National Laboratory

Matrix partitioning is used to reduce communication and balance the 
workload in parallel computations involving sparse matrices.  
Substantial effort has gone into developing partitioning schemes and 
software for sparse, structurally symmetric matrices.  However, 
scant attention has been paid to the rectangular and structurally 
nonsymmetric cases.  Rectangular and structurally nonsymmetric 
matrices arise in many situations including the solution of 
nonsymmetric linear systems, large-scale SVD computations, linear 
programming, etc.  We will present a bipartite graph model for 
partitioning rectangular matrices and describe new methods for 
partitioning this type of graph with numerical results.  Lastly, 
we'll discuss the matrix partitioning problem in general and new 
work that is going on in the area.  

(This is joint work with Bruce Hendrickson of Sandia National Labs.)