Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction $p_k$? I know the set of search directions are supposed to be conjugate with respect to A. One way to generate such sets is using the eigenvectors of A, but this is very computationally expensive. Another way is to use modified Gram Schmidt, but this requires so much storage. Hence, we choose $p_{k+1}=-r_k+\beta p_k$... but why this choice?

  • 1
    $\begingroup$ You want to choose the directions so that (i) they are easy to compute, i.e., no eigenvectors for example, and (ii) they do not require much memory storage. With the given linear combination, all you need to store is the previous search direction, the current residual, and the current search direction. $\endgroup$ Jan 17 '15 at 22:57
  • 2
    $\begingroup$ Because it's easy to pick $\beta$ so that $p_{k+1}Ap_k$ is zero. $\endgroup$
    – Bill Barth
    Jan 17 '15 at 22:57
  • 2
    $\begingroup$ "Why does this work" and "how did they come up with this" are two different questions, with frequently completely unrelated answers. For the latter, this paper may be of interest: epubs.siam.org/doi/abs/10.1137/1031003?journalCode=siread $\endgroup$ Jan 18 '15 at 0:54
  • 2
    $\begingroup$ To expand on Bill Barth's comment: The whole point of the CG method is to avoid the need to orthogonalize the new search direction against all previous directions; the key observation was that this is possible if one doesn't work with the standard Euclidean inner product but the one induced by the matrix $A$ (building on the work of Lanczos, who gave an algorithm to reduce a symmetric positive definite matrix to a tridiagonal matrix, which can be seen as a variant of Gram-Schmidt for the $A$-inner product). $\endgroup$ Jan 18 '15 at 1:10
  • 1
    $\begingroup$ Is this useful? cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf $\endgroup$
    – Subodh
    Jan 21 '15 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.