A Study of the Effects of Ordering, Partitioning and Factorization Algorithms on Distributed Sparse Cholesky Factorization
Report ID: TR-505-96Author: Raghavachari, Mukund / Rogers, Anne
Date: 1996-01-00
Pages: 17
Download Formats: |Postscript|
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.