A Fast Parallel Cholesky Decomposition Algorithm for Tridiagonal Symmetric Matrices

In this paper we present a new parallel algorithm for computing the Cholesky decomposition (LL^T) 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 \hat{x}_k and \hat{x}'_k denote the components computed in the preprocessing stage and the corresponding values (re)computed in the factorization stage, respectively. Assuming that \abs{\hat{x}_k/\hat{x}'_k} 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 \abs{\hat{x}_k/\hat{x}'_k} 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.