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

Thank you!

• 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. – Kevin Dalmeijer Aug 2 '20 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 '20 at 15:49