# Why is this version of the algorithm more efficient?

I am a student self-studying Optimization, and I am reading about the Conjugate Gradient Method in Numerical Optimization by Nocedal & Wright, and they present two different algorithms for it. First they present Algorithm 5.1 which is the way you might first implement the Conjugate Gradient Method based on the mathematical theory. Then, they do a few mathematical tricks to change the formula for some variables, and claim that the new Algorithm 5.2 is more efficient.

I tried comparing the algorithms, and I don't see why the second is significantly more efficient than the first. The only formulas which are different are the ones for $$\alpha_k, r_{k+1},$$ and $$\beta_{k+1}.$$

In the formula for $$\alpha_k$$, the only change is that we have replaced the inner product $$-r_k^Tp_k$$ with $$r_k^T r_k$$, and I don't see why this would make a difference.

In the formula for $$r_{k+1}$$, I guess I see one efficiency. Instead of computing the matrix product $$Ax_{k+1},$$ we can use $$Ap_k$$, a quantity which we already had to calculate in computing $$\alpha_k$$.

In the formula for $$\beta_{k+1}$$, we first replaced $$r_{k+1}^TAp_k$$ with $$r_{k+1}^Tr_{k+1}$$. Since, as discussed above, we already know the product $$Ap_k$$, I don't see why this is more efficient. Second, we replaced $$p_k^TAp_k$$ by $$r_k^Tr_k$$, which, for the same reason, doesn't appear to be more efficient.

There must be something I'm missing; could you please help me identify it?

Thank you!  • In the wikipedia article en.m.wikipedia.org/wiki/Conjugate_gradient_method they talk about this Aug 1, 2020 at 16:15
• It would help if you stated the problem being solved.
– prubin
Aug 1, 2020 at 18:01
• The book says that Algorithm 5.2 is a 'slightly more economical form of the conjugate gradient method'. The fact that $Ax_{k+1}$ does not need to be calculated may be sufficient for that. Another efficiency could be that the value of $r_{k+1}^\top r_{k+1}$ can be reused in the next iteration as $r_k^\top r_{k}$ after $k$ is incremented by one. But I don't know if this saving is any significant in practice. Aug 2, 2020 at 13:33
• @prubin Oh I'm sorry, the Conjugate Gradient Method is used to solve the linear system $Ax = b$ with $A$ symmetric and positive definite (or equivalently) minimizing the function $\varphi(x) = \frac 12 x^TAx - b^Tx$, again with $A$ symmetric and positive definite.
– Blue
Aug 2, 2020 at 15:49
• Maybe I'm misreading something but I tried coding both versions in R and running them on a small test problem, and the first method converged much faster than the second.
– prubin
Aug 3, 2020 at 22:53