Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Bill Barth Jan 9 '12 at 16:10
    
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. –  shuhalo Jan 13 '12 at 10:32

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
1  
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). –  Jack Poulson Jan 9 '12 at 16:25

A related question that might be of interest is Which sparse linear system solver to use?, 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.

share|improve this answer

MINRES is the best choice for this type of problem.

share|improve this answer
1  
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. –  Jed Brown Jan 9 '12 at 15:59
    
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. –  Geoff Oxberry Jan 12 '12 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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