A Distributed Multifrontal Algorithm Using Clique Trees
Alex Pothen, Chunguang Sun · 1991
We describe a parallel multifrontal sparse Cholesky factorization algorithm for distributed-memory multiprocessors that makes use of the clique tree to organize the factorization. A new task-toprocessor mapping algorithm applicable to general sparse problems is problems is described, and its performance is compared with the only general mapping algorithm that has been proposed previously. In our experiments on a collection of problems from the Boeing-Harwell test set, we obtain efficiencies comparable to those obtained for the model grid problem. We obtain a characterization of the clique tree of the grid problem, and thereby compute the maximum and minimum arithmetic and communication that a processor is responsible for. The arithmetic and communication requirements of the distributed multifrontal algorithm are shown to be balanced and asymptotically optimal for the model problem.