## Encapsulating Multiple Communication-Cost Metrics in Partitioning Sparse Rectangular Matrices for Parallel Matrix-Vector Multiplies

### Bora Uçar and Cevdet Aykanat

Abstract. This paper addresses
the problem of one-dimensional partitioning of structurally
unsymmetric square and rectangular sparse matrices for parallel
matrix-vector and matrix-transpose-vector multiplies. The objective is
to minimize the communication cost while maintaining the balance on
computational loads of processors. Most of the existing partitioning
models consider only the total message volume hoping that minimizing
this communication-cost metric is likely to reduce other
metrics. However, the total message latency (start-up time) may be
more important than the total message volume. Furthermore, the maximum
message volume and latency handled by a single processor are also
important metrics. We propose a two-phase approach that encapsulates
all these four communication-cost metrics. The objective in the first
phase is to minimize the total message volume while maintaining the
computational-load balance. The objective in the second phase is to
encapsulate the remaining three communication-cost metrics. We propose
communication-hypergraph and partitioning models for the second
phase. We then present several methods for partitioning communication
hypergraphs. Experiments on a wide range of test matrices show that
the proposed approach yields very effective partitioning results. A
parallel implementation on a PC cluster verifies that the theoretical
improvements shown by partitioning results hold in practice.

Key words. matrix partitioning, structurally unsymmetric matrix, rectangular matrix, iterative method, matrix-vector multiply, parallel computing, message volume, message latency, communication hypergraph, hypergraph partitioning

AMS Subject Classifications. 05C50, 05C65, 65F10, 65F50, 65Y05