01 October 2011

Fastest Krylov method for symmetric indefinite problems?

One of my engineer correspondents asked what Krylov subspace method would be fastest for solving a symmetric indefinite problem: GMRES, a least-squares solver such as LSQR, or BiCG.  I've thought about this a lot for symmetric positive definite problems, but not so much for the indefinite case.  Here are my thoughts; i welcome correction or further suggestions.

BiCG reduces to a redundantly computed CG if the matrix is symmetric positive definite.  Thus, CG should always be faster than BiCG in that case.  I haven't thought about this question before for the case of a symmetric indefinite problem, but my guess is that MINRES would be faster than BiCG (or, say, QMR) in most cases.  MINRES promises monotonic convergence of the residual norm; BiCG doesn't.  Their storage requirements are comparable.

MINRES is a special case of GMRES for symmetric indefinite problems.  MINRES should be faster than GMRES, though MINRES is a bit less robust.

LSQR works a little bit like BiCG (it builds up two Krylov bases).  My guess is that MINRES would be faster than LSQR.

If the linear system is singular or very ill conditioned, one may have more success with LSQR than with GMRES, more success with GMRES than with MINRES, and more success with MINRES than SYMMLQ.  LSQR is able to solve rank-deficient problems in a least-squares sense.  GMRES and MINRES (depending on the implementation) may be able to solve rank-deficient problems in a least-squares sense.

On the other hand, "LSQR with preconditioning" means something rather different than users might think.

Alas, I want to write more, but time constrains me...