3
$\begingroup$

I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here.

I understand that for many iterative methods, convergence rates can be shown to depend on the condition number of the coefficient matrix $A$ in the linear equation $$Ax=y.$$ Therefore, if a preconditioner satisfies $P \approx A$, then by solving the transformed linear equation $$(AP^{-1}) (Px)=y.$$ the new coefficient matrix will now have more favorable spectral properties and hence better convergence can be achieved.

One of the main properties a good preconditioner should satisfy besides the above condition is that its inverse should be cheap to apply. Thus, they are often sought out for with a certain structure. Typical examples are the incomplete Cholesky and LU factorizations of the matrix $A$.

My question is: why do we want to have $P \approx A$, or, in a more direct approach, why do we formulate finding preconditioners as: $$ \min_{P} \left\| AP^{-1} - I \right\|_F, $$ where $F$ represents the Frobenius-norm? The identity matrix isn't the only one with a condition number of 1; would it not be better to formulate the problem as: $$ \min_{P,Q} \left\| AP^{-1} - Q \right\|_F, $$ with $Q$ having to be orthogonal? Given a certain structure restriction on $P$, I imagine this would lead to better preconditioning than in the previous case.

$\endgroup$
  • 1
    $\begingroup$ I think this could benefit from migration to scicomp.SE. $\endgroup$ – David Ketcheson Dec 1 '16 at 4:39
1
$\begingroup$

The Frobenius norm remains the same if we do the orthogonal transform, so $$ \min_{P,Q} \left\| AP^{-1} - Q \right\|_F = \min_{P,Q} \left\| Q^{-1}AP^{-1} - I \right\|_F $$ which is essentially nothing more than a two-sided preconditioning. While for some reason you consider only right-sided in the beginning (usually I see the left preconditioning but it depends on the problem, of course).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very true! I considered right-sided preconditioning because I originally thought about this when having a non-square matrix with more rows than columns. I understand that right-sided ones are preferred in such a case due to their smaller size, correct? $\endgroup$ – Tusike Dec 1 '16 at 21:54
0
$\begingroup$

The answer is that looking for a matrix such that $AP^{-1} \approx I$ is a simplification. The convergence speed of Krylov subspace methods depends heavily on the clustering of eigenvalues of $AP^{-1}$ (in the normal case at least; in the non-normal case it's not that clear but clustering eigenvalues seems to be a good proxy).

If you ensure that $\|AP^{-1}-I\|$ is small, then you also automatically ensure that the eigenvalues are clustered around 1. But that's not the only possibility.

Some preconditioning strategies for saddle-point problems, for instance, aim to obtain a matrix with three clusters of eigenvalues around $1, \frac{1+\sqrt5}2,\frac{1-\sqrt5}2$, and some others aim to obtain two clusters around $-1$ and $1$.

On the other hand, $AP^{-1}$ being orthogonal does not ensure faster convergence. The classical counterexample is the system (after preconditioning) $$ \begin{bmatrix} 0 & && & 1\\ 1 & 0 & \\ & 1 & 0 & \\ & & \ddots & \ddots \\ & & & 1 & 0 \end{bmatrix}x = \begin{bmatrix} 1\\0\\0\\\vdots\\0 \end{bmatrix}, $$ in which Arnoldi methods stagnate for $n-1$ steps and then converge abruptly in the last one.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the Conjugate Gradient method, though, convergence rate is proportional to the square root of the condition number. Or to just the condition number if I have a least squares problem and am applying one of its corresponding variants e.g. LSQR. Does the clustering matter in such a case as well? $\endgroup$ – Tusike Dec 1 '16 at 22:24
  • 1
    $\begingroup$ @Tusike Yes, it does matter greatly; the bounds based on $\kappa$ are a simplification, too. Clustering dictates the true convergence behavior. See for instance in onlinelibrary.wiley.com/doi/10.1002/gamm.201490008/pdf: the bound (15) cannot be identified with the CG convergence, and it represents an overestimate even of the worst-case behavior except for very special eigenvalue distributions in the given interval, and the following example. $\endgroup$ – Federico Poloni Dec 2 '16 at 7:22

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.