A Comparison of Parallel Solvers for Diagonally Dominant and General Narrow-Banded Linear Systems

Abstract

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 and those investigated by Arbenz and Hegland. 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.