With CG, the preconditioner also needs to be SPD (or have suitable factors).  You can get by pretty well using only GMRES and spend all your time thinking about preconditioners.  Once you have some good candidate preconditioners, you can try other Krylov methods, but the gains are rarely very large.  I have frequently found SPD systems that are more efficiently solved with GMRES and a non-symmetric preconditioner, and even more so for symmetric indefinite systems where popular wisdom says to use MINRES, CR, or SQMR.<p>For amusement, it's really worth knowing about<p><a href="http://www.comlab.ox.ac.uk/people/nick.trefethen/publication/PDF/1992_52.pdf" rel="nofollow">http://www.comlab.ox.ac.uk/people/nick.trefethen/publication...</a><p>which shows that each of the popular nonsymmetric iterations can beat all others by a huge factor.<p>But this is all justification that you should use a library like PETSc for your linear solvers.  Then all aspects of the solve become run-time (typically command-line) options including an algebra for composing preconditioners and other components, with a plugin architecture for every component.