关键词: 并行计算 稀疏矩阵乘以向量 负载平衡

Abstract:

In this paper, we consider the load-balancing multiplication of a large sparse matrix with a large sequence of vectors on parallel computers. We propose a load-balancing algorithm based on non-zero values even the allocation of the sequence rows of sparse matrices. The complexity of this algorithm is O（N）, where N is the number of rows in the matrix. In contrast to the best current algorithm with the complexity of O（N · P）, where P is the numberr of processors, the performance of our approach is much better. Especially, because our algorithm is based on the sequence row allocation of sparse mat  rices, we can conveniently compose the parallel code and optimize the communications.

Key words: parallel eomputing;sparse matrix-vector multiplication, load balancing