3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.