# Optimality of block-Jacobi preconditioner

For a dense $$N \times N$$ matrix $$A$$, is the block-Jacobi preconditioner comprising the inverse of the diagonal blocks of $$A$$ the optimal block-diagonal preconditioner? Could there exist another matrix $$P$$ with the same sparsity pattern whose product $$PA$$ does a better job of reining in the small eigenvalues of $$A$$?

Consider matrix a $$2\times 2$$ matrix $$A$$:

$$A=\left(\begin{array}{cc} 1 & 0\\ 2 & 1 \end{array}\right)$$

Singular values of $$A$$ are: $$\sigma_1 = \sqrt{2}+1,\quad \sigma_2=\sqrt{2}-1$$

resulting in the condition number (2-norm) $$\kappa_2(A)=3+2\sqrt{2}$$.

If we consider a block-diagonal Jacobi preconditioner $$J=I_2$$ with block-size 1 (which effectively makes it a diagonal or plain Jacobi preconditioner):

$$JA=I_2A \implies \kappa_2(JA) = \kappa_2(A)=3+2\sqrt{2}\approx5.828$$

Here, $$I_2$$ denotes an identity matrix of size 2.

Now, if we are able to find a matrix $$P$$ that has the same structure as $$J$$ (diagonal for our example), such that $$\kappa_2(PA)<\kappa_2(JA)$$, then we can say that $$J$$ is not an optimal block-diagonal preconditioner.

Let's consider $$P$$, as follows:

$$P(x,y)=\left(\begin{array}{cc} x & 0 \\ 0 & y \end{array} \right)$$ and run it through an optimizer with a goal to minimize $$\kappa_2(PA)$$. I was able to achive $$\kappa_2(PA)\approx4.236$$ with $$x\approx 0.401$$ and $$y\approx 0.179$$.

So, with this brute-force approach, we were able to find $$P$$ with the same structure as $$J$$, which leads to a better 2-norm condition number.

You can also take a look at the discussion at Mathematics SE which conveys that

there is no simple relation for the optimal diagonal scaling which minimizes the spectral condition number of a matrix except for several special cases

Since this is true for a diagonal scaling (Jacobi), it should be true for the block-diagonal as well. That answer also talks about formulation for the optimal scaling leading to a convex optimization problem $$\implies$$ not sure if there is work like that for the general block-diagonal scaling (with block size $$\neq$$ 1).