A two-dimensional data distribution method for parallel sparse matrix-vector multiplication. (English) Zbl 1083.65044

It is well known that sparse matrix-vector multiplication is the central part of many numerical algorithms, especially iterative solvers for systems of linear equations. In case of distributed memory parallel computers, the performance of such solvers can be improved when we design a suitable distribution of the data and the associated work.
The authors present a 2D method for partitioning sparse matrices and a method for partitioning the input and the output vectors that attempts to balance the communication volume among processors. The method is based on a recursive bipartitioning of the sparse matrix by splitting it into two parts with a nearly equal number of nonzero elements. Numerical tests of the method with respect to a set of sparse test matrices are also presented and discussed. The paper is also an excellent introduction to sparse matrices on parallel computers.


65F30 Other matrix algorithms (MSC2010)
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI