A Study of the Effects of Ordering, Partitioning and Factorization Algorithms on Distributed Sparse Cholesky Factorization

Abstract:

In this paper, we perform a comprehensive evaluation of ordering,
partitioning, and factorization algorithms under a unified framework.
Previous research in distributed, sparse Cholesky factorization has
considered each of the stages in the factorization process --- ordering,
partitioning and numerical factorization --- in isolation. However, due to
the strong dependencies between the stages, it is difficult to derive
conclusions from such an approach.
Specifically, in our experiments, we use input files representative of
practical problems to study the benefits and shortcomings of ordering
algorithms --- multiple minimum degree and spectral nested dissection,
column-based partitioning algorithms --- wrapped mapping and proportional
mapping, and block-based partitioning. We use, as the base for our
experiments, three factorization algorithms: Fanin, Fanout and Block Fanout.
In addition, we extend the research of Rothbergq by performing an in-depth
analysis of the advantages of panel-based partitionings versus column-based
partitionings on message-passing machines. All experiments were run on a
Thinking Machines CM-5.