9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you say a bit more about what makes your matrices special? E.g. what kind of problem does it come from? Is there any other kind of structure to it? Etc. Etc. $\endgroup$
    – Bill Barth
    Jan 9, 2012 at 16:10
  • $\begingroup$ I have left it intentionally blank, to get the most general answer (frankly, this implicitly assumes there is a satisfying general answer). But the example with the Helmholtz equation below is fairly what I had in mind. $\endgroup$
    – shuhalo
    Jan 13, 2012 at 10:32

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ To be fair, while the sweeping preconditioners are certainly technical to implement efficiently in parallel, the idea is not specific to Helmholtz; the main requirement is an absorbing boundary condition (e.g., Perfectly Matched Layers). $\endgroup$ Jan 9, 2012 at 16:25
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

MINRES is the best choice for this type of problem.

$\endgroup$
2
  • 1
    $\begingroup$ Please do not link your personal site this way. Feel free to link specific resources that are relevant to your answer, but do not link your personal site this way. I have removed it from this answer. Such links belong on your user profile. $\endgroup$
    – Jed Brown
    Jan 9, 2012 at 15:59
  • 1
    $\begingroup$ Could you please elaborate on why MINRES is the best choice for this type of problem? Adding more detail will help make your answer more useful to the community, and will help get you more up votes. $\endgroup$ Jan 12, 2012 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.