A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor
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.
large sparse symmetric positive definite matrix
parallel symbolic Cholesky factorization algorithm
message-passing hypercube multiprocessor
scientific article; zbMATH DE number 4068161