A NEW BIDIRECTIONAL CHOLESKY FACTORIZATION ALGORITHM FOR PARALLEL SOLUTION OF SPARSE SYMMETRICAL POSITIVE-DEFINITE SYSTEMS

In this paper, we consider the problem of solving sparse linear system s occurring in finite difference applications (or N x N grid problems, N being the sire of the linear system). We propose a new algorithm fo r the problem which is based on the Cholesky factorization, a symmetri c variant of Gaussian elimination tailored to symmetric positive defin ite systems. The algorithm employs a new technique called bidirectiona l factorization to produce the complete solution vector by solving onl y one triangular system against two triangular systems in the existing Cholesky factorization after the factorization phase. The effectivene ss of the new algorithm is demonstrated by comparing its performance w ith that of the existing Cholesky factorization for solving regular fi nite difference grid problems on hypercube multiprocessors.