Hello, Your site is great. Regards, Valintino Guxxi

It is interesting that this technique was used until 1960's, then were forgotten until recently. I think the remedy that brought it back is the introduction of periodic restarts. Otherwise, error build-up would cause the search vectors to lose their A-orthogonality for complex problems.

Edited by author 10-07-2004 03:54 PM
Unfortunately, upon first exposure to a topic I usually need a couple of readings to digest the material. So my comments/questions are probably not very insightful.

1. How would one show that performing conjugation on the axial unit vectors makes Conjugate Directions equivalent to Gaussian Elimination? Is there any geometric intuition here? (p. 26)

2. I think the key to understanding the CG method as presented in this paper is understanding section 7.3 Optimality of the Error Term. Luck has it, though, that I do not yet completely follow the author's discussion.

Interesting. How does it compare to other optimization techniques, such as EM?

To answer Robin's question about the size of the problems that conjugate gradient is used to handle. Think BIG, by big here we are talking about simulations containing millions of variables and going upto potentially a billion variables.

Since Vincent brought up Bi-Conjugate gradient, the folks who brought us the various pieces of software like LINPACK and LAPACK, also bring us

Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM Press

http://netlib2.cs.utk.edu/linalg/html_templates/Templates.html

This is a comprehensive reference and comparison of the various techniques that go into solving large linear systems.

In case the history of Conjugate Gradient is of interest, there is a rather remarkable article in SIAM reviews (part of JStor)

Gene H. Golub; Dianne P. O'Leary

SIAM Review, Vol. 31, No. 1. (Mar., 1989), pp. 50-102.

Stable URL: http://links.jstor.org/sici?sici=0036-1445...OTCG%3E2.0.CO%3B2-S

Well since you asked,
you do not need to do any hacks for to get symmetric positive semi-definiteness. Instead of solving
Ax = b
consider the system

A^\top A x = A^\top b

Section 13 of the paper discusses this. In case you are wondering if A^\top A is still sparse or not, turns out there is no need to ever actually form A^\top A explicitly. Simple Matrix vector products suffice.

So what is the downside?, well condition number for A^\top A is the square of the condition number of A, and hence convergence is slower.

cool paper. A bit long, but half of it is just basics of linear algebra so that is fine.
So, this seems cool to solve Ax=b when A is symmetric positive definite, but what is done when it is not the case ? Is there a way of modifying a bit the method like it was done in this fantastic talk on tuesday on LM ? (like you "add" enough to A to have it symmetric positive definite; you find a solution; then you do something with the original A). Or maybe something can only be done if the matrix is purely symmetric, purely positive...
Briefly: how generalizable is it ? (I've heard of biconjugate gradient method but I am not sure of its application)

Robin, it is indeed a very well written explanation with a lot of pre-requisites well covered.

Louka, That was my first reaction too, but he does go into a lot of depth, including preconditioning and use of CG to solve nonlinear problems. And he doesn't leave you with a long list of undefined terms to look up!

Most intriguing for me was that CG is used to tackle really large relaxation problems. How large, I wonder? (If you tell me to think big, I'm just likely to do it, so what's a realistic target?) And how much sparsity does it take for this method to be a good choice? The nonlinear use seemed less appealing because you have to keep restarting it. But maybe if one doesn't have any other good choices, those restarts are a small price to pay?

The title of the paper is "An Introduction to the Conjugate Gradient Method _Without the Agonizing Pain_". It's 64 pages long. How ironic is that? ;)