Take the 2-minute tour ×

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|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
add comment

1 Answer

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|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 wise..like 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
add comment

Your Answer


