Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've the following problem.I've a sparse square Matrix $\bf M$. I can write $\bf M$ as: $${\mathbf M} = \begin{bmatrix}\mathbf A_{11} & \dots & \mathbf A_{1n} \\ \vdots & \ddots & \vdots \\ \mathbf A_{n1} & \dots & \mathbf A_{nn}\end{bmatrix}$$ where each of the $\mathbf A_{ij}$ is a sparse (symmetric). It's like (but not exactly) the one we would get if we solve the Poisson equation in 2D (5 neighbours). I've following cases..

  1. When in total $\mathbf M$ is symmetric and positive definite
  2. When $\mathbf M$ is only symmetric but not positive definite.

Now my questions are: For case (1) and For case (2) separately: What kind of iterative method must I use to solve the linear system ${\mathbf M}\mathbf x=\mathbf b$? Currently I'm doing it with CG but I want to go for PCG. So can anyone comment on what kind of preconditioner is best for faster convergence suitable to the above problem? My only criterion is faster convergence.


share|cite|improve this question
Why don't you use a block-diagonal preconditioned: diag$(A_{11}^{-1},...,A_{nn}^{-1})$? At first glance, this seems to be a sensible choice... – Hauke Strasdat Aug 10 '12 at 16:57

The purpose of preconditioning is to make the eigenvalues as similar as possible, since conjugate gradient search works best for similar eigenvalues (ideally in one step if all eigenvalues are the same). The precondition matrix should try to broadly mimic the spectrum of $\mathbf M$.

In the Poisson case, $\mathbf M$ is exactly diagonalized by a Fourier transform. You could Fourier transform your matrix, and if it's similar to the Poisson matrix, you should get a nearly diagonal matrix; then you can use the diagonal part of that for preconditioning.

share|cite|improve this answer
Thank you for the suggestion , But still could anyone comment/give me some reference to some papers or books on using any special kind of method (for ex iterative methods solving block in domain decomposition cases..) to solve such kind of linear systems..DO such kind of linear systems fall into any special category ..??? – Sameer Sen Aug 10 '12 at 17:44
@Sameer: Sorry, I'm not an expert on any of that -- it's been $13$ years that I did preconditioned conjugate gradient search... – joriki Aug 10 '12 at 20:16

Your Answer


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.