The scheduling of sparse matrix-vector multiplication on a massively parallel DAP computer (Q1199098)

The performance of some possible data structures and associated matrix- vector multiplication schemes for representing unstructured sparse matrices on the masivelly parallel architecture of the distributed array of processors (DAP) is examined with the aim to reduce the interprocessor data transfer. The parallel performance measures are number of DAP size floating point multiplications respectively additions. The repeated matrix-vector multiplication is considered on the DAP, using the same matrix in each iteration. Particular block partitioned allocation methods such as the method of \textit{M. Morjaria} and \textit{G. J. Makinson} [Unstructured sparse matrix vector multiplication on the DAP. Super Computers and Parallel Computation 1984, 157-166 (1984)], the extended stacking scheme and the block banded schemes are tested on the matrix `stair'. The motivation is an efficient parallel computation of the main algorithmic step of the interior point method for solving large scale linear programming (LP) problems, i.e. solving symmetric positive systems of linear equations. For the SIMD machine architecture an iterative conjugate gradient solver has been used because this method can be reduced to repeated matrix-vector multiplications. Various versions of sparse algorithms are tested and evaluated on 8 well-known LP problems.