Jacobi preconditioner versus unit-row or unit-column preconditioner

234 Views Asked by At

Given the system $Ax=b$, where $A$ is square and has only positive eigenvalues, one can solve the system using the preconditioned modified Richardson iteration: $x^{k+1} = (I-\omega M^{-1}A)x^k + \omega M^{-1}b$ with $\omega \in \left(0,\frac{2}{\rho(M^{-1}A)}\right)$, provided $M^{-1}A$ also has only positive eigenvalues. A popular choice is Jacobi preconditioning: $M^{-1} = (\operatorname{diag}(A))^{-1}$, which makes $M^{-1}A, AM^{-1}, M^{-\frac{1}{2}}AM^{-\frac{1}{2}}$ have unit diagonals. Is there any difference between the last three preconditioners? For example in terms of the condition number or the spectral radius? Are the spectral radii equal? Is there a proof that this preconditioning keeps the eigenvalues positive?

Now consider two alternative preconditioners $R^{-1}A$ or $AC^{-1}$ which normalize every row or column: $R_{ii} = \operatorname{diag}(\sum_j|A_{ij}|)$ or $C_{jj} = \operatorname{diag}(\sum_i|A_{ij}|)$. These preconditioners make it so that $\rho(R^{-1}A)\leq\|R^{-1}A\|_{\infty}=1$ and $\rho(AC^{-1})\leq\|AC^{-1}\|_1=1$. Are there any references comparing these to Jacobi and results on the condition number of the preconditioned matrix?

Edit: Thanks to Carl Chrisitian pointing out that the matrices are similar I have: $$M^{\frac{1}{2}}(M^{-1}A)M^{-\frac{1}{2}} = M^{-\frac{1}{2}}AM^{-\frac{1}{2}} = M^{-\frac{1}{2}}(AM^{-1})M^{\frac{1}{2}}$$

which means that the eigenvalues and thus spectral radii agree. This also means that $R^{-1}A$ and $AC^{-1}=AR^{-1}$ are similar (also $R^{-\frac{1}{2}}AR^{-\frac{1}{2}}$) if $A$ is symmetric. The Jacobi preconditioner $M^{-1}$ and row-wise $R^{-1}$/column-wise $C^{-1}$ one are equivalent in the case $A$ has the exact same value in each row/column.

Regarding the relationship between Jacobi, the spectral radius, and the condition number I found this: Relations between condition numbers and the convergence of the Jacobi method for real positive definite matrices