Communication Cost of Sparse Cholesky Factorization on a Hypercube
Abstract
The authors consider the nested dissection ordering of a k x k grid of nodes and the Cholesky factorization of the associated k squared x k squared symmetric matrix. When the factorization is computed on a hypercube machine with p processors then the communication cost (the total number of nonzero elements that need to be communicated among the processors) can be kept down to O (pk squared) when the processors are assigned appropriately. This result was proved in George, Liu and Ng (1987). We offer a simple proof of a slightly stronger result: the communication cost for each processor is O (k squared). Load balancing is built into our proof. Our argument extends to grids in more than 2 dimensions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA206860
Entities
People
- Beresford N. Parlett
- Fei Gao
Organizations
- University of California, Berkeley