Iterative methods for indefinite systems without block structure

Question

Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form

$$\begin{pmatrix} A & B^t \\ B & C\end{pmatrix}$$

where $A$ is negative (semi)-definite, $C$ is positive (semi-) definite and $B$ is arbitrary. Of course, depending on convention you may use definiteness conditions, but this is pretty much the structure of those matrices.

For these methods, Uzawa's method can be employed, which is actually just a "trick" to transform the system into an equivalent semi-definite system that can be solved by Conjugate Gradient, Gradient Descent and the like.

I face an indefinite system which does not have such a block structure. Uzawa-type methods do not apply in that case. I am aware of the Minimal Residual method (MINRES) that has been introduced by Paige & Saunders, which is just a three-term recursion and seems to be easy to implement.

Question: Is MINRES generally a good choice, say, for prototyping? Is it of any practical relevance? Preconditioning is no central issue at the moment.

Answer 1

If you are not concerned about preconditioning, then MINRES is the standard choice. However, be aware that MINRES requires a symmetric positive definite preconditioner.

If you are concerned with preconditioning, then it is important to consider the structural differences between most saddle point problems and general indefinite problems. Most saddle point problems arise when solving elliptic problems with constraints enforced by Lagrange multipliers. Incompressibility and contact constraints are common examples. For such problems, the operator is coercive on the subspace in which the constraint is satisfied, with Green's functions that decay rapidly. Such problems can be solved efficiently using block preconditioners (preconditioned Uzawa is a member of this family), multigrid with compatible smoothers (e.g. Vanka or based on block decomposition), or multilevel domain decomposition with appropriate local and coarse problems.

The prototypical example of an indefinite problem that is not a saddle point problem is the Helmholtz equation

$$ -\nabla\cdot \big( a \nabla u \big) - k^2 u = f $$

where $a(x)$ is uniformly bounded above and below by positive constants. For $k$ large, the Green's functions are highly oscillatory which makes preconditioning (and discretization) difficult. Two reasonable approaches are sweeping preconditioners based on perfectly matched layers and "wave-ray multigrid", as described in answers to this question. Unfortunately, these methods are rather custom for a specific equation and technical to implement.

Answer 2

A related question that might be of interest is What guidelines should I follow when choosing a sparse linear system solver?, although in this case, you would be interested in only the iterative methods. My understanding of iterative methods is that convergence for any given method is heavily dependent on the spectrum of your matrix. Even though you can't use Uzawa's method, you could still try GMRES, Biconjugate stabilized gradient, MINRES, the quasi-minimal residual method, and other iterative methods out there that apply to indefinite matrices.

If coding the various methods is a concern, you could call solvers in your algorithm using a library like PETSc, which implements a variety of iterative linear solvers.

Answer 3

MINRES is the best choice for this type of problem.