Computational models and task scheduling for parallel sparse Cholesky factorization (Q1086977)

The numerical solution of linear systems has the following typical phases: ordering, symbolic factorization, numeric factorization, and numeric substitution. In this paper the numeric factorization phase for parallel computation is studied. A parallel sparse Cholesky factorization algorithm is formulated. It is suitable for parallel machines with shared-memory architecture, like Denelcor HEP. The algorithm is based on the medium-grained graph model of column-oriented tasks and a critical path type of scheduling. A variant of the scheme allowing preemption is also described. The algorithm assumes that the given matrix has already been ordered by some fill-reducing ordering algorithm, e.g. the minimum degree ordering.