并行计算稀疏矩阵乘以向量的负载平衡算法

A Load-Balancing Algorithm for Sparse Matrix-Vector Multiplication on Parallel Computers

稀疏矩阵乘以一个向量(SpM×V)的问题是许多大型应用问题的核心计算问题,文中提出了一种在并行计算机上并行计算SpM×V的负载平衡算法,计算复杂性为O(N)(N为稀疏矩阵的阶),而目前计算此类问题的最优负载平衡算法的计算复杂性为O(N.P)(P为处理机台数)。文章最后给出了并行数值实验。

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 number of processors, the performance of our approach is much better. Especially, because our algorithm is based on the sequence row allocation of sparse matrices, we can conveniently compose the parallel code and optimize the communications.