LOAD-BALANCED SPARSE MATRIX-VECTOR MULTIPLICATION ON PARALLEL COMPUTERS

We considered the load-balanced multiplication of a large sparse matri x with a large sequence of vectors on parallel computers, We propose a method that combines fast load-balancing with efficient message-passi ng techniques to alleviate computational and inter-node communications challenges. The performance of the proposed method was evaluated on b enchmark as well as on synthetically generated matrices and compared w ith the current work. It is shown that, by using our approach, a tangi ble improvement over prior work can be obtained, particularly for very sparse and skewed matrices, Moreover, it is also shown that I/O overh ead for this problem can be efficiently amortized through I/O latency hiding and overall load-balancing. (C) 1997 Academic Press.