Problems where Conjugate gradient works much better than GMRES

Question

I am interested in cases where Conjugate gradient works much better than GMRES method.

In general, CG is preferable choice in many cases of SPD (symmetric-positive-definite) because it requires less storage and theoretical bound on convergence rate for CG is double of that GMRES. Are there any problems where such rates are actually observed? Is there any characterization of cases where GMRES performs better or comparable to CG for same number of spmvs (sparse matrix-vector multiplications).

Answer 1

One thing that CG has in its favor is that it's not minimizing the discrete $l^2$ norm for its residual polynomials (what GMRES does). It's minimizing a matrix-induced norm instead, and very often this matrix-induced norm ends up being very close to the energy norm for discretizations of physical problems, and frequently this is a much more reasonable norm to measure error in because of conservation properties coming from the physics.

You can actually achieve this sort of effect with GMRES too if performing a Cholesky factorization of a mass matrix isn't too expensive, you can force the inner products to be the energy inner products you want.

Then the cases where one should expect CG to perform very differently from GMRES then is when the constants implied in norm equivalence are very different. This can be true for example in a high order spectral-Galerkin method where the discrete $l^2$ norm used in GMRES treats all degrees of freedom as being equal, when in reality polynomial gradients are sharpest near boundaries (hence node clustering), and so the norm equivalence constants between that norm and say the continuous $L^2$ norm given by the mass matrix can be very large.

Answer 2

I suspect there is in general not much difference between GMRES and CG for an SPD matrix.

Let's say we are solving $ Ax = b $ with $ A $ symmetric positive definite and the starting guess $ x_0 = 0 $ and generating iterates with CG and GMRES, call them $ x_k^c $ and $ x_k^g $. Both iterative methods will be building $ x_k $ from the same Krylov space $ K_k = \{ b, Ab, A^2b, \ldots \} $. They will do so in slightly different ways.

CG is characterized by minimizing the error $ e_k^c = x - x_k^c $ in the energy norm induced by $ A $, so that \begin{equation} (A e_k^c, e_k^c) = (A (x - x_k^c), x - x_k^c) = \min_{y \in K} (A (x-y), x-y). \end{equation}

GMRES minimizes instead the residual $ r_k = b - A x^g_k $, and does so in the discrete $ \ell^2 $ norm, so that \begin{equation} (r_k, r_k) = (b - A x_k^g, b - A x_k^g) = \min_{y \in K} (b - Ay, b - Ay). \end{equation} Now using the error equation $ A e_k = r_k $ we can also write GMRES as minimizing \begin{equation} (r_k, r_k) = (A e_k^g, A e_k^g) = (A^2 e_k^g, e_k^g) \end{equation} where I want to emphasize that this only holds for an SPD matrix $ A $. Then we have CG minimizing the error with respect to the $ A $ norm and GMRES minimizing the error with respect to the $ A^2 $ norm. If we want them to behave very differently, intuitively we would need an $ A $ such that these two norms are very different. But for SPD $ A $ these norms will behave quite similarly.

To get even more specific, in the first iteration with the Krylov space $ K_1 = \{ b \} $, both CG and GMRES will construct an approximation of the form $ x_1 = \alpha b $. CG will choose \begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation} and GMRES will choose \begin{equation} \alpha = \frac{ (Ab,b) }{ (A^2b,b) }. \end{equation} If $ A $ is diagonal with entries $ (\epsilon,1,1,1,\ldots) $ and $ b = (1,1,0,0,0,\ldots) $ then as $ \epsilon \rightarrow 0 $ the first CG step becomes twice as large as the first GMRES step. Probably you can construct $ A $ and $ b $ so that this factor of two difference continues throughout the iteration, but I doubt it gets any worse than that.

Answer 3

One thing is that GMRES is never used wherever CG can be applied. I dont think it does make sense to compare these two. For SPD matrices, CG is definitely the winner because of the storage requirements and the reasons you mentioned above. A question that would be interesting is, to find an extension of CG, that is applicable to problems where CG can not be applied. There are methods like BiCG-stab that do not require linearly increasing memory like GMRES, but the convergence is not as good as GMRES (some times even with restarted GMRES).