Class ConjugateGradient


public class ConjugateGradient extends PreconditionedIterativeLinearSolver

This is an implementation of the conjugate gradient method for RealLinearOperator. It follows closely the template by Barrett et al. (1994) (figure 2.5). The linear system at hand is A · x = b, and the residual is r = b - A · x.

Default stopping criterion

A default stopping criterion is implemented. The iterations stop when || r || ≤ δ || b ||, where b is the right-hand side vector, r the current estimate of the residual, and δ a user-specified tolerance. It should be noted that r is the so-called updated residual, which might differ from the true residual due to rounding-off errors (see e.g. Strakos and Tichy, 2002).

Iteration count

In the present context, an iteration should be understood as one evaluation of the matrix-vector product A · x. The initialization phase therefore counts as one iteration.

Exception context

Besides standard MathIllegalArgumentException, this class might throw MathIllegalArgumentException if the linear operator or the preconditioner are not positive definite.

  • key "operator" points to the offending linear operator, say L,
  • key "vector" points to the offending vector, say x, such that xT · L · x < 0.

References

Barret et al. (1994)
R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. M. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine and H. Van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM
Strakos and Tichy (2002)
Z. Strakos and P. Tichy, On error estimation in the conjugate gradient method and why it works in finite precision computations, Electronic Transactions on Numerical Analysis 13: 56-80, 2002