from Hacker News

Introduction to the Conjugate Gradient Method Without Agonizing Pain (1994) [pdf]

by chmike on 8/13/23, 12:23 PM with 15 comments

• by trostaft on 8/13/23, 2:20 PM

  I remember being handed this back when I was taking numerical analysis for the first time. It's an old document, but still useful.

  IMO the critical pieces of CG that make it a favorable choice for many problems in scientific computing are

  1) the fact that it can be performed matrix free

  2) its rapid convergence behavior on operators with clusters of eigenvalues (useful for low rank structures)

  Thet being said, practically speaking, even if I know my operator is positive semi definite, I often find minres out performing cg. There's a nice paper comparing that, "CG versus MINRES: An Empirical Comparison".

• by fastneutron on 8/13/23, 2:36 PM

  Shewchuk’s work on mesh generation is nothing short of a masterpiece. I will always direct people to the source of his Triangle code as an example of what good, literate C code should look like. His Berkeley page is here: https://people.eecs.berkeley.edu/~jrs/

• by mnw21cam on 8/13/23, 2:12 PM

  I cited this in my doctoral thesis. I'm not sure the title is accurate though. It doesn't manage to remove the "this bit is magic, just do the exact incantations and it'll work out" feel from it.

• by aqme28 on 8/13/23, 5:39 PM

  Important to note that this method only works on Hermitian (usually AKA symmetric) and positive-definite matrices, both of which are often pretty big qualifiers.

• by hazrmard on 8/13/23, 4:44 PM

  Thank you! I first came across Conjugate Gradient when reviewing the paper on Neural Ordinary Differential Equations. It was quite challenging to parse through that math. This helps.

• by gh02t on 8/13/23, 2:14 PM

  Hah, my professor was using this as a reference in my numerical methods class circa 2010. It's a great one, highly recommended.