A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor (Q1108738)

Consider a system of linear algebraic equations \(Ax=b\), where A is an \(n\times n\) large sparse symmetric positive definite matrix. Solving it for x the Cholesky factor L of A is computed first and then the systems \(Ly=b\) and \(L^ Tx=y\) are solved, where L is the lower triangular matrix such that \(A=LL^ T\). A parallel algorithm is developed for computing elimination forests and its correctness is proved. Using this algorithm a new parallel symbolic Cholesky factorization algorithm is presented for a message-passing hypercube multiprocessor and its complexity is discussed.