7
$\begingroup$

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!

enter image description here

enter image description here

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ In the wikipedia article en.m.wikipedia.org/wiki/Conjugate_gradient_method they talk about this $\endgroup$
    – user3680510
    Commented Aug 1, 2020 at 16:15
  • $\begingroup$ It would help if you stated the problem being solved. $\endgroup$
    – prubin ♦
    Commented Aug 1, 2020 at 18:01
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kevin Dalmeijer
    Commented Aug 2, 2020 at 13:33
  • $\begingroup$ @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. $\endgroup$
    – Blue
    Commented Aug 2, 2020 at 15:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Aug 3, 2020 at 22:53

1 Answer 1

Reset to default
1
$\begingroup$

Computational complexity depends somewhat on the number of elementary calculations performed. The least troublesome is the addition of two integers. A more complex is the multiplication of two floating point numbers (several times more processor ticks). Then multiplication of a vector by a number, multiplication of two vectors, multiplication of a vector by a matrix, multiplication of two matrices, etc.

Both versions of the algorithm differ by two equations 5.14c, 5.24c or 5.14d, 5.24d. While equation 5.24c requires additional multiplication by a number, matrix multiplication operations disappear in the 5.24d.

It is essential in the implementation that basic operations are performed through specially optimized linear algebra library routines (e.g. BLAS, ATLAS, etc).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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