Parallel solution of large narrow band linear systems

A novel algorithm for the fast parallel iterative solution of large narrow band matrices on shared memory systems is presented. For this, a new parallel many-block factorization is developed for block tridiagonal systems. In the process, several new results are obtained for relationships between norms, antinorms, and spectral radii of block matrices. Using these, it is shown that under very mild assumptions, for all iterative solvers such that the spectral radius of the iteration matrix varies monotonically with that of the Jacobi matrix, iterations on a system preconditioned using the proposed factorization converges faster than on the original system. In particular, under some mild assumptions, preconditioned Jacobi iterations converge about four times faster in terms of number of iterations. To achieve near-optimal parallel performance, our factorization is coupled with the block stair SOR algorithm to develop a new algorithm, each iteration of which is roughly comparable to an iteration of the former in computational complexity. A minimal workspace is required and our algorithm converges asymptotically optimally in time, and has better parallel performance than block stair SOR for large matrices. Moreover, it is observed numerically that small deviations of the overrelaxation parameter from its optimal value only have a relatively small effect on the number of iterations needed to converge. Finally, numerical data is presented that demonstrates a reduction in the condition number of our test system post-factorization. To conclude, possible methods to further speed up performance and a potential extension to distributed memory systems are discussed.