Finding optimal ordering of sparse matrices for column-oriented parallel Cholesky factorization (Q1402303)

The problem of finding fill-preserving sparse matrix orderings for parallel factorization is considered. That is, given a large sparse symmetric and positive definite matrix that has been ordered by some fill-reducing ordering, a reordering is determined that is appropriate in terms of preserving the sparsity, and minimizing the cost to perform the Cholesky factorization in parallel. Based on the column task graph, a greedy reording algorithm is devised, and it is proved that the algorithm can find the corresponding optimal ordering among the class of all fill-preserving orderings of the given matrix.