19
$\begingroup$

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

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wanted to give an example here with a high order method and convergence histories of CG, GMRES, and GMRES+Cholesky trick.. but unfortunately the only code I have on hand for second order problems is DG of the nonsymmetric variety.. so CG isn't applicable, would love to see this in action. $\endgroup$
    – Reid.Atcheson
    May 2, 2013 at 2:48
  • 3
    $\begingroup$ I think your answer gets at something important but I wish you would clarify. In particular, the question is a pure linear algebra question, and your answer talks about physical norms and mass matrices and so on from a numerical PDE. Can we say something precise about how minimizing in different norms within the same Krylov space leads to different iterates? $\endgroup$
    – Andrew T. Barker
    May 2, 2013 at 12:12
  • 1
    $\begingroup$ Aside from numerical examples I don't think there has been yet a careful theoretical study explaining how different norms yield substantially different answers. The issue I think is that results revolve around asymptotics, and for a fixed linear system the theoretical results will be identical modulo constant factors. If there are some theoretical studies out there I'd love to see them, but having asked some of the numerical linear algebra experts in my department it doesn't seem that there is yet a precise theoretical analysis showing what happens with different norms. $\endgroup$
    – Reid.Atcheson
    Jul 8, 2013 at 5:27
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Let $b = (1,\sqrt{\epsilon},0,0,\dotsc)$. Then $|b| = \sqrt{1 + \epsilon}$, $b^T A b = \sqrt{2} \epsilon$, and $b^T A^2 b = \epsilon \sqrt{1 + \epsilon^2}$. Thus $\alpha_{\text{CG}} = \frac{\epsilon^{-1}+1}{\sqrt 2} \sim \epsilon^{-1}$, but $\alpha_{\text{GMRES}} = \sqrt{\frac{2}{1 + \epsilon^2}} \sim \sqrt{2}$. That is, the initial vector is already of the correct scale for making the residual small, but needs to be scaled by $\epsilon^{-1}$ to make the error small. $\endgroup$
    – Jed Brown
    May 15, 2013 at 12:32
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ There are the IDR schemes which bridge the gap between GMRES and BiCG in terms of memory savings, stability, and convergence: ta.twi.tudelft.nl/nw/users/gijzen/IDR.html I'm not sure I agree that GMRES shouldn't be used if CG could be. If you can do a cholesky factorization of a matrix which induces your energy norm, then you can feed that into a symmetric Lanczos iteration and obtain a three term recurrence solution that will behave very nearly like CG. Of course, CG is the easier option, but the option is available :) $\endgroup$
    – Reid.Atcheson
    May 2, 2013 at 3:08
  • 2
    $\begingroup$ If you use a Krylov smoother, for instance, then GMRES is likely preferable because it uses a weaker norm that targets larger eigenvalues which tend to be higher frequency. $\endgroup$
    – Jed Brown
    May 2, 2013 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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