Parallel Solution of Symmetric Banded Systems.

H.X. Lin and M. R. Roest Parallel Algorithms Group, TWI/TA, Delft University of Technology, Mekelweg 4, 2628 CD DELFT, the Netherlands An efficient parallel method is presented for the solution of symmetric banded sys­tems through Cholesky factorization. The proposed algorithm, called ParChol (Parallel Cholesky factorization) algorithm, is better suited for banded systems than known sparse matrix factorization algorithms. Analysis shows that the ParChol algorithm achieves linear speedup since the communication overhead and the sequential fraction of the op­erations are small. For a matrix with dimension n and semi-bandwidth fe, the parallel factorization time on a computer with p processors is o{~) for p < {n/b)/\og{n/b). The efficiency is C(l), which readily indicates that the algorithm is efficient. 1. INTRODUCTION In many applications, a given symmetric banded linear system Ax = y has to be solved for many right-hand side vectors y. This can be done by first performing a Cholesky factorization of the matrix, after which the solution for each vector y can be found by solving two triangular systems. On sequential computers, the computation of a Cholesky factorization takes 0{n.b'^) time. Much effort has been put in finding good parallel algo­rithms for this problem. Most of the work is based on [2], which considers the problem of parallel sparse matrix Cholesky factorization. The basic idea is to work on different columns in parallel if possible. Improved versions of the original algorithm have been reported in e.g. [3] and [4]. However, for banded matrices with no zero-elements within the band, the speedup of these algorithms can be no more then To increase the speedup factor, Bar-On [1] has designed a parallel Cholesky factoriza­tion algorithm with a theoretical time complexity of 0{~-) using p < (w/6)/log(n/6) processors. Unfortunately, the resulting triangular factor with the same structure as the original bandmatrix is not very suited for parallel triangular solution. The maximum speedup is 0{b) unless a lot of extra work is performed ( the total amount of operations is then increased to 0(n.6^) from that of 0{n.b) for sequential triangular solution). The parallel Cholesky factorization algorithm that is presented in this paper has the same theoretical time complexity but gives factors that allow efficient triangular solution. Furthermore, the required communication is Hmited. In the next section, the ParChol algorithm will be described, the efficiency of the parallel forward and back substitution will be indicated and a few remarks will be made on the data distribution.