Abstract:
Krylov subspace solvers for linear systems of equations are well-known and widely used in computational sciences. The conjugate gradient (CG) method is the grandfather of those solvers, and most researchers have seen its mathematical derivation and theorems about convergence rates. This talk will concentrate on the numerical behaviour of the algorithm, and try to explain some features in numerical computing which seem to violate the mathematical properties that CG has in exact arithmetic. Those features include having the residual error not monotonically decreasing, why the condition number of a linear system is not a good predictor of how well CG works, and why it sometimes can take many more or many fewer iterations than the theory predicts.
Although shown primarily for the CG algorithm, the ideas also apply to nonsymmetric Krylov solvers. CG is used here because it allows some illuminating visualizations, which will also be presented. No theorems will be proved, instead examples and heuristics will be used to help in understanding CG's behaviour.
I'll use some Matlab scripts to illustrate most of the features, and will provide them to anyone who wants them. Unfortunately, in keeping with computer science tradition they are poorly documented, but the talk should help explain them.