The average parallel complexity of Cholesky factorization
type: Item
instance of: scholarly article
title: The average parallel complexity of Cholesky factorization
zbMATH Open document ID: 0755.65033
DOI: 10.1016/0898-1221(91)90204-H
publication date: 1992-09-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 60606
zbMATH Keywords: symbolic factorization
zbMATH Keywords: numerical factorization
zbMATH Keywords: solution of triangular systems
zbMATH Keywords: average-case performance
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: sparse symmetric matrices
zbMATH Keywords: minimum degree ordering
zbMATH Keywords: parallel complexity
zbMATH Keywords: numerical experiments
zbMATH Keywords: random matrices
zbMATH Keywords: average depth of the elimination tree
zbMATH Keywords: direct factorizations
zbMATH Keywords: sparse matrices
author: Giovanni Resta
describes a project that uses: symrcm
MaRDI profile type: Publication
cites work: The Evolution of the Minimum Degree Ordering Algorithm
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: Q5185900
cites work: On the Number of Nonzeros Added when Gaussian Elimination is Performed on Sparse Random Matrices
cites work: Q3682518
cites work: Q3664299
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 60606