Parallel symbolic factorization of sparse linear systems

The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log²n) time using m* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First it finds A's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log²n) time using m processors, where m is the number of nonzeros in A.