Minimum communication cost reordering for parallel sparse Cholesky factorization

✍ Scribed by Wen-Yang Lin; Chuen-Liang Chen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 279 KB
• Volume: 25
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00027-7

✦ Synopsis

In this paper, we consider the problem of reducing the communication cost for the parallel factorization of a sparse symmetric positive de®nite matrix on a distributed-memory multiprocessor. We de®ne a parallel communication cost function and show that, with a contrived example, simply minimizing the height of the elimination tree is ineective for exploiting minimum communication cost and the discrepancy may grow in®nitely. We propose an algorithm to ®nd an ordering such that the communication cost to complete the parallel Cholesky factorization is minimum among all equivalent reorderings. Our algorithm consumes yn log n m in time, where n is the number of nodes and m the sum of all maximal clique sizes in the ®lled graph.