A tree model for sparse symmetric indefinite matrix factorization. (English) Zbl 0653.65021
While in the factorization of large sparse symmetric positive definite matrices the order of elimination may be chosen to minimize fill-in without regard to stability, for indefinite matrices some sort of pivoting may be necessary. The author studies the diagonal pivoting method, which preserves symmetry but uses a mixture of 1*1 and 2*2 pivots, in the context of delayed elimination. A graph theoretic method, the elimination tree, is used to investigate the factorization process. It may be viewed as a sequence of tree transformations, influenced both by the sparsity structure as well as the actual numerical values of the pivots. Some possibilities for implementing the tree model are discussed at the end.
Reviewer: H.Matthies
MSC:
65F05 | Direct numerical methods for linear systems and matrix inversion |
65F50 | Computational methods for sparse matrices |
15A23 | Factorization of matrices |