The average parallel complexity of Cholesky factorization (Q1192153)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The average parallel complexity of Cholesky factorization |
scientific article |
Statements
The average parallel complexity of Cholesky factorization (English)
0 references
27 September 1992
0 references
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.
0 references
symbolic factorization
0 references
numerical factorization
0 references
solution of triangular systems
0 references
average-case performance
0 references
Cholesky factorization
0 references
sparse symmetric matrices
0 references
minimum degree ordering
0 references
parallel complexity
0 references
numerical experiments
0 references
random matrices
0 references
average depth of the elimination tree
0 references
direct factorizations
0 references
sparse matrices
0 references