A fast parallel cholesky decomposition algorithm for tridiagonal symmetric matrices

In this paper we present a new parallel algorithm for computing the LL(T) decomposition of real symmetric positive-definite tridiagonal matrices. The algorithm consists of a preprocessing and a factoring stage. In the preprocessing stage it determines a rank-(p - 1) correction to the original matrix (p,= number of processors) by precomputing selected components x(k) of the L factor, k = 1,...,p - 1. In the factoring stage it performs independent factorizations of p matrices of order n/p. The algorithm is especially suited for machines with both vector and processor parallelism, as confirmed by the experiments carried out on a Connection Machine CM5 with 32 nodes. Let <(x)over cap(k)>, and <(x)over cap'(k)> denote the components computed in the preprocessing stage and the corresponding values (re)computed in the factorization stage, respectively. Assuming that is small, k = 1,...,p-1, we are able to prove that the algorithm is stable in the backward sense. The above assumption is justified both experimentally and theoretically. In fact, we have found experimentally that is small even for ill-conditioned matrices, and we have proven by an a priori analysis that the above ratios are small provided that preprocessing is performed with suitably larger precision.