Solving Hermitian positive definite systems using indefinite incomplete factorizations

Incomplete LDL* factorizations sometimes produce an indenite preconditioner even when the input matrix is Hermitian positive denite. The two most popular iterative solvers for symmetric systems, CG and MINRES, cannot use such preconditioners; they require a positive denite preconditioner. One approach, that has been extensively studied to address this problem is to force positive deniteness by modifying the factorization process. We explore a dierent approach: use the incomplete factorization with a Krylov method that can accept an indenite preconditioner. The conventional wisdom has been that long recurrence methods (like GMRES), or alternatively non-optimal short recurrence methods (like symmetric QMR and BiCGStab) must be used if the preconditioner is indenite. We explore the performance of these methods when used with an incomplete factorization, but also explore a less known Krylov method called PCG-ODIR that is both optimal and uses a short recurrence and can use an indenite preconditioner. Furthermore, we propose another optimal short recurrence method called IP-MINRES that can use an indenite preconditioner, and a variant of PCG-ODIR, which we call IP-CG, that is more numerically stable and usually requires fewer iterations.

By: Haim Avron; Anshul Gupta; Sivan Toledo

Published in: RC25191 in 2011

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

rc25191.pdf

Questions about this service can be mailed to reports@us.ibm.com .