A parallel algorithm for sparse symbolic Cholesky factorization on a multiprocessor. (English) Zbl 0654.65025
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.
Reviewer: L.Bakule
MSC:
65F05 | Direct numerical methods for linear systems and matrix inversion |
65Y05 | Parallel numerical computation |
15A23 | Factorization of matrices |