AN EFFICIENT PARALLEL ALGORITHM FOR MATRIX-VECTOR MULTIPLICATION

The multiplication of a vector by a matrix is the kernel operation in many algorithms used in scientific computation. A fast and efficient p arallel algorithm for this calculation is therefore desirable. This pa per describes a parallel matrix-vector multiplication algorithm which is particularly well suited to dense matrices or matrices with an irre gular sparsity pattern. Such matrices can arise from discretizing part ial differential equations on irregular grids or from problems exhibit ing nearly random connectivity between data structures. The communicat ion cost of the algorithm is independent of the matrix sparsity patter n and is shown to scale as O(n/root p + log(p)) for an n x n matrix on p processors. The algorithm's performance is demonstrated by using it within the well known NAS conjugate gradient benchmark. This resulted in the fastest run times achieved to date on both the 1024 node nCUBE 2 and the 128 node Intel iPSC/860. Additional improvements to the alg orithm which are possible when integrating it with the conjugate gradi ent algorithm are also discussed.