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.

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

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

• 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? – Tusike Dec 1 '16 at 21:54

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.

• 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? – Tusike Dec 1 '16 at 22:24
• @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. – Federico Poloni Dec 2 '16 at 7:22