A comparison of parallel solvers for diagonally dominant and general narrow-banded linear systems
Peter Arbenz, Andrew J. Cleary, Jack J. Dongarra, Markus Hegland · Repository for Publications and Research Data (ETH Zurich) · 1998
. We investigate and compare stable parallel algorithms for solving diagonally dominant and general narrow-banded linear systems of equations. Narrow-banded means that the bandwidth is very small compared with the matrix order and is typically between 1 and 100. The solvers compared are the banded system solvers of ScaLAPACK [11] and those investigated by Arbenz and Hegland [3, 6]. For the diagonally dominant case, the algorithms are analogs of the well-known tridiagonal cyclic reduction algorithm, while the inspiration for the general case is the lesser-known bidiagonal cyclic reduction, which allows a clean parallel implementation of partial pivoting. These divide-and-conquer type algorithms complement fine-grained algorithms which perform well only for wide-banded matrices, with each family of algorithms having a range of problem sizes for which it is superior. We present theoretical analyses as well as numerical experiments conducted on the Intel Paragon. Key words. narrow-banded ...