Minimum communication cost reordering for parallel sparse Cholesky factorization

摘要

In this paper, we consider the problem of reducing the communication cost for the parallel factorization of a sparse symmetric positive definite matrix on a distributed-memory multi- processor. We define a parallel communication cost function and show that, with a contrived example, simply minimizing the height of the elimination tree is ineffective for exploiting minimum communication cost and the discrepancy may grow infinitely. We propose an al- gorithm to find an ordering such that the communication cost to complete the parallel Cholesky factorization is minimum among all equivalent reorderings. Our algorithm con- sumes O(n logn + m) in time, where n is the number of nodes and m the sum of all maximal clique sizes in the filled graph.