The average parallel complexity of Cholesky factorization (Q1192153)

The author considers average-case performance of Cholesky factorization of sparse symmetric matrices using the minimum degree ordering. In particular, the parallel complexity (which is based on the number of eliminations that can be performed simultaneously at each stage) is examined. Using a combination of simple probabilistic analysis and numerical experiments on random matrices, the author conjectures that the average depth of the elimination tree after the minimum degree ordering has been applied is \(O(n \log n)\) (where \(n\) is the order of the matrix). Moreover, after \(O(\log n)\) stages of ``parallel'' elimination, a nearly- dense submatrix of dimension \(O(n)\) remains -- an observation that has significant implications for codes that implement direct factorizations of sparse matrices.