On signed incomplete Cholesky factorization preconditioners for saddle-point systems

• ID: 2774, RIV: 10361158
• ISSN: 1064-8275, ISBN: not specified
• source: SIAM Journal on Scientific Computing
• keywords: sparse matrices; sparse linear systems; positive-definite symmetric systems; iterative solvers; preconditioning; incomplete Cholesky factorization.
• authors: Miroslav Tůma, Jennifer Scott
• authors from KNM: Tůma Miroslav

Abstract

Limited-memory incomplete Cholesky factorizations can provide robust precondi- tioners for sparse symmetric positive-definite linear systems. In this paper, the focus is on extending the approach to sparse symmetric indefinite systems in saddle-point form. A limited-memory signed incomplete Cholesky factorization of the form LDLT is proposed, where the diagonal matrix D has entries +-1. The main advantage of this approach is its simplicity as it avoids the use of numerical pivoting. Instead, a global shift strategy involving two shifts (one for the (1, 1) block and one for the (2, 2) block of the saddle-point matrix) is used to prevent breakdown and to improve performance. The matrix is optionally prescaled and preordered using a standard sparse matrix ordering scheme that is then post-processed to give a constrained ordering that reduces the likelihood of breakdown and need for shifts. The use of intermediate memory (memory used in the construction of the incom- plete factorization but subsequently discarded) is shown to significantly improve the performance of the resulting preconditioner. Some new theoretical results are presented and for problems arising from a range of practical applications, numerical results are given to illustrate the effectiveness of the signed incomplete Cholesky factorization as a preconditioner. Comparisons are made with a recent incomplete LDLT code that employs pivoting.