Title
Effective Preconditioning through Ordering Interleaved with Incomplete Factorization
Abstract
Consider an incomplete Cholesky factorization of a sparse symmetric positive definite matrix. It is common practice to start with a symmetric permutation of the rows and columns of the matrix using an ordering to reduce fill in the complete Cholesky factor. Such an approach has two drawbacks. First, such an ordering is designed to reduce fill or operation counts in the complete Cholesky factor, and thus does not necessarily address the issue of controlling fill or operation counts during incomplete factorization. Second, because the ordering is determined in advance of the incomplete factorization, it is not easy to accommodate alternative pivoting sequences, for example, using numeric measures to promote stability, while taking into account their impact on fill and operation counts. In this paper, we consider an alternative approach that interleaves ordering with numeric computation in an incomplete Cholesky factorization. Such an interleaved scheme controls fill and operation counts. It also allows the incorporation of some limited, pivot selection strategies for stability. We demonstrate through experiments that our interleaved minimum-degree approach leads to fewer failures during incomplete factorization and improved convergence when the incomplete factor is used as a preconditioner for the conjugate gradient method. We conjecture that the improvements in the quality of preconditioning arise from the ability of our method to generate better approximations to the complete factor.
Year
DOI
Venue
2006
10.1137/040618357
SIAM J. Matrix Analysis Applications
Keywords
Field
DocType
complete factor,incomplete cholesky factorization,incomplete factorization,alternative pivoting sequence,operation count,interleaved minimum-degree approach,incomplete factor,alternative approach,complete cholesky factor,effective preconditioning,conjugate gradient method,ordering,preconditioner
Conjugate gradient method,Mathematical optimization,Incomplete Cholesky factorization,Minimum degree algorithm,Symmetric matrix,Factorization,Incomplete LU factorization,Sparse matrix,Mathematics,Cholesky decomposition
Journal
Volume
Issue
ISSN
27
4
0895-4798
Citations 
PageRank 
References 
9
0.89
9
Authors
3
Name
Order
Citations
PageRank
Ingyu Lee1528.90
Padma Raghavan246077.54
Esmond Ng350391.55