THE DESIGN, IMPLEMENTATION, AND EVALUATION OF A SYMMETRICAL BANDED LINEAR SOLVER FOR DISTRIBUTED-MEMORY PARALLEL COMPUTERS

This article describes the design, implementation, and evaluation of a parallel algorithm for the Cholesky factorization of symmetric banded matrices. The algorithm is part of IBM's Parallel Engineering and Sci entific Subroutine Library version 1.2 and is compatible with ScaLAPAC K's banded solver. Analysis, as well as experiments on an IBM SP2 dist ributed-memory parallel computer, shows that the algorithm efficiently factors banded matrices with wide bandwidth. For example, a 31-node S P2 factors a large matrix more than 16 times faster than a single node would factor it using the best sequential algorithm, and more than 20 times faster than a single node would using LAPACK's DPBTRF. The algo rithm uses novel ideas in the area of distributed dense-matrix computa tions that include the use of a dynamic schedule for a blocked systoli c-like algorithm and the separation of the input and output data layou ts from the layout the algorithm uses internally. The algorithm also u ses known techniques such as blocking to improve its communication-to- computation ratio and its data-cache behavior.