On evaluating elimination tree based parallel sparse cholesky factorizations

Abstract

Though a variety of parallel sparse Cholesky factorizations have been developed and diverse experiments on various machines have been reported, there is still a lack of theoretical evaluations because of the irregular structure of sparse matrices. This study is an effort on such research. On the basis of the elimination tree model, we compared the computation and communication perspective of four widely adopted parallel Cholesky factorization methods, including column-Cholesky, row-Cholesky, submatrix-Cholesky and multifrontal. The results show that the multifrontal method is superior to the others.

Keywords:

• Distributed-memory multiprocessor
• sparse matrix
• parallel factorization
• equivalent reordering
• elimination tree

AMS Subject Classifications:

• 05C50
• 65F50
• 65Y05

C.R. Categories:

• G1.3
• F2.1
• G2.2