The average parallel complexity of Cholesky factorization (Q1192153): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: symrcm / rank | |||
Normal rank |
Revision as of 09:44, 29 February 2024
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