Optimality of block-Jacobi preconditioner

Question

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$?

Answer 1

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