Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Since Residual history is only available, in many cases to judge how well an algorithm has performed, would GMRES have always lower residual norm than CG in that case?

share|improve this question
1  
This is probably not apt for MO. You should probably try scicomp.stackexchange.com. –  user11000 May 1 '13 at 4:09
2  
From the look of it, yes, but there is probably a completely theoretical question in matrix approximation theory hidden behind this one. –  Federico Poloni May 1 '13 at 7:14

1 Answer 1

The short answer is for SPD matrices, CG and GMRES are formally the same. The long answer is that they have differ in their numerical stability so your mileage varies in practice when your matrix begins to be even mildly ill-conditioned.

Definition 1 (Krylov subspace). Given the system of equations $Ax=b$, the m-th Krylov subspace is defined $$\mathcal{K}_m(A,b)=\mathrm{span}(b,Ab,A^2b,\ldots,A^{m-1}b).$$

Let us write $K_m\in\mathbb{R}^{n\times m}$ as the orthogonal basis matrix for $\mathcal{K}_m$. Then for symmetric positive-definite $A$, both CG and GMRES solve the following at the m-th iteration: $$H\hat{x}=\hat{b},$$ where $H\in\mathbb{R}^{m\times m},\hat{x},\hat{b}\in\mathbb{R}^m$ are the projections of $A,x$ and $b$ onto the m-th Krylov space, $$H=K_m^TAK_m,\qquad\hat{x}=K_m^Tx,\qquad\hat{b}=K_m^Tb,$$ thereby minimizing the residual vector $r_m = b - K_m\hat{b}$ against the m-th Krylov space.

Where they differ is how $K_m$ is computed, since spanning the Krylov space is an inherently ill-conditioned problem. GMRES does this using Lanczos iterations, while CG takes a number of important shortcuts. When the conditioning of $A$ is more than ~100, these differences start affecting the actual values of $K_m$, and this results in a difference in convergence rates. The shortcuts in CG make it more efficient but less stable.

Finally, to convince you that I'm not making this up, here's a picture of CG and GMRES sharing the exact same residual norms at each iteration for a randomly generated well-conditioned dense problem.

CG and GMRES having the same residual norms

Original code:

A = rand(100); b = rand(100,1);
A = A+A'+eye(100)*50;
[x,~,~,~,resvec] = gmres(A,b,[],0,5);
[x2,~,~,~,resvec2] = pcg(A,b,0,5);
semilogy(1:6,resvec,'-x',1:6,resvec2,'-o');
xlabel('Iteration number');
ylabel('Residual norm');
legend('GMRES','PCG')

Finally, for more detailed info, I would highly recommend CT Kelley's book, "Iterative Methods for Linear and Nonlinear Equations". The author has generously made the pdf available on SIAM for noncommercial use. http://www.siam.org/books/textbooks/fr16_book.pdf

share|improve this answer
    
Conjugate gradient minimizes residual's A-norm in $\mathcal{K}_{m}$, while GMRES minimizes residual's $\mathcal{L}_{2}$ norm –  zimbra314 Dec 3 at 0:34
    
Sure, consider $\min_\hat{x} \|K_m^T(Ax-b)\|, x=K_m\hat{x}$, which is solved at each iteration of either algorithm. I claim that for $m<n$, there is a unique solution $\hat{x}$ that sets any norm to zero. That is, there exists an $\hat{x}\in\mathbb{R}^m$ such that $K_m^T(AK_m\hat{x}-b)=0$, where $0$ is the zero vector in $\mathbb{R}^m$. In this case, it does not matter which norm we take, we would obtain the same unique solution up to numerical round-off. –  Richard Zhang Dec 3 at 19:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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