Talk:Conjugate gradient method

Mistake ?

In sections 'The conjugate gradient method as an iterative method' and 'The resulting algorithm', the definition of alpha changes from p.r to r.r. Is this intentional ? The p.r version is correct, right ? - max. —Preceding unsigned comment added by 78.226.234.207 (talk) 08:50, 14 October 2010 (UTC)

Comment

In your algorithm, the formula to calculate pk differs from Jonathan Richard Shewchuk paper. The index of r should be k instead of k-1. Mmmh, sorry, it seams to be correct! ;-) —The preceding unsigned comment was added by 171.66.40.105 (talk • contribs) 01:45, 21 February 2007 (UTC)

Minor point about quadratic forms

Is x'A'x + b'x really a quadratic form? It's not homogeneous, and my understanding is that quadratic forms must be homogeneous. Note that this is just a usage quibble; I have no complaint about the math. Birge (talk) 03:26, 16 May 2009 (UTC)

It is not according to "Quadratic form". I have made the modifications.Kxx (talk) 05:48, 16 May 2009 (UTC)

Small error in code

"end if" causes a sintax error in Octave. Should be "endif" or just "end". Italo Tasso (talk) 20:05, 20 July 2009 (UTC)

Major conceptual flaw

The article gives the impression that you need to keep in memory all vectors calculated in order to find a new one that is conjugate to all the previous ones, but this is not true. The vectors are calculated one by iteration and based just on the previous one, and this is precisely one of the most important aspects of the whole theory.

Yes it's that awesome, it's not a simplification, it's not a crazy new direction conjugate just to the last one, it really is conjuge to all previous in spite of we throwing them away! And it must be made clear that the algorithm is direct _and_ iterative. Sometimes you can have good approximations before the last step, and stop before, but this approximate algorithm is otherwise identical to the direct version. -- NIC1138 (talk) 05:04, 11 April 2010 (UTC)

It already mentions that, but is simply too vague in doing so. Kxx (talk | contribs) 06:09, 11 April 2010 (UTC)

I would love to see more discussion of this. I admit, much as I've tried to understand this algorithm, the details of why you only need O(n) memory and O(n) per iteration illude me. It is pretty darn cool "magic" and could really do with more explanation. —Ben FrantzDale (talk) 13:56, 12 April 2010 (UTC)

Yousef Saad's book has a fairly detailed coverage of CG from the perspective of specialization of the Arnoldi iteration, including derivation of the three-term recurrences, of course. PDF of the first edition is online at Saad's homepage. You can check it out. Kxx (talk | contribs) 20:23, 12 April 2010 (UTC)

Original research in "description" section?

The "description" section has always been painfully confusing to whoever wants to understand the theory behind the conjugate gradient method as the two "as a direct/iterative method" subsections provide nothing close to the actual algorithm, which is only vaguely justified with a cryptic paragraph at the beginning of the "resulting algorithm" subsection.

It now seems even worse to me that a large portion of the section appears to consist of pure original research—although the equations are true, nobody derives the conjugate gradient method that way, i.e., expressing the solution as a linear combination of the search directions and then calculating coefficients. (Let's not mention the "numerical example" subsection, which is probably the most obvious OR offender.) I looked at Hestenes and Stiefel's paper and Jonathan Shewchuk's writing, which are close in the way of thinking. But they describe the method as a special case of the conjugate direction method, which readily gives the expressions for α_i and x_i, no need for linear expansion.

Probably the best way out is a rewrite. Just follow either or both of the two classical derivations (conjugate direction method and Lanczos iteration). Kxx (talk | contribs) 20:12, 13 April 2010 (UTC)