ON FAST FACTORIZATION PIVOTING METHODS FOR SPARSE SYMMETRIC INDEFINITE SYSTEMS 论文

摘要

This paper discusses new pivoting factorization methods for solving sparse symmetric indenite sys- tems. As opposed to many existing pivoting methods, our SupernodenBunchnKaufman (SBK) pivoting method dy- namically selects and pivots and may be supplemented by pivot perturbation techniques. We demonstrate the effectiveness and the numerical accuracy of this algorithm and also show that a high performance implementa- tion is feasible. We will also show that symmetric maximum-weighted matching strategies add an additional level of reliability to SBK. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques during the numerical factorization. Numerical experiments validate these conclusions. where is a diagonal matrix with and pivot blocks, is a sparse lower triangu- lar matrix, and is a symmetric indenite diagonal matrix that reects small half-machine precision perturbations, which might be necessary to tackle the problem of tiny pivots. is a reordering that is based on a symmetric weighted matching of the matrix , and tries to move the largest off-diagonal elements directly alongside the diagonal in order to form good initial or diagonal block pivots. is a ll reducing reordering which honors the structure of . We will present three new variations of a direct factorization scheme to tackle the is- sue of indeniteness in sparse symmetric linear systems. These methods restrict the pivoting search, to stay as long as possible within predened data structures for efcient Level-3 BLAS factorization and parallelization. On the other hand, the imposed pivoting restrictions can be reduced in several steps by taking the matching permutation into account. The rst al- gorithm uses SupernodenBunchnKaufman (SBK) pivoting and dynamically selects and pivots. It is supplemented by pivot perturbation techniques. It uses no more storage than a sparse Cholesky factorization of a positive denite matrix with the same sparsity structure due to restricting the pivoting to interchanges within the diagonal block associated to a single supernode. The coefcient matrix is perturbed whenever numerically acceptable and pivots cannot be found within the diagonal block. One or two steps of iterative re- nement may be required to correct the effect of the perturbations. We will demonstrate that this restricting notion of pivoting with iterative renement is effective for highly indenite symmetric systems. Furthermore the accuracy of this method is for a large set of matrices from different applications areas as accurate as a direct factorization method that uses com- plete sparse pivoting techniques. In addition, we will discuss two preprocessing algorithms to identify large entries in the coefcient matrix that, if permuted close to the diagonal, permit