Iterative Method for a special kind of Sparse Matrix

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.

Regards,

-
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.
@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