Matrix-vector multiplication and conjugate gradient algorithms on distributed memory computers

The critical bottlenecks in the implementation of the conjugate gradient algorithm on distributed memory computers are the communication requirements of the sparse matrix-vector multiply and of the vector recurrences. In a previous paper (G. Lewis et al., 1993), we described the data distribution and communication patterns of several implementations of parallel matrix-vector multiplication, demonstrating that on hypercubes, the cost of communication can be overcome to a much larger extent than is often assumed. In this paper, we generalize the best of those implementations to mesh architectures. We make no assumptions about the mesh being square or power-of-two. We also comment on the implications of our results for structured problems and on the scalability of our approach. Results are presented for the implementation of these algorithms on the Intel Touchstone Delta and Paragon mesh multicomputers