Package org.hipparchus.linear

Class ConjugateGradient

java.lang.Object

org.hipparchus.linear.IterativeLinearSolver

org.hipparchus.linear.PreconditionedIterativeLinearSolver

org.hipparchus.linear.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 x^T · 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

Field Summary

Fields

Modifier and Type	Field	Description
static String	OPERATOR	Key for the exception context.
static String	VECTOR	Key for the exception context.

Constructor Summary

Constructors

Constructor	Description
ConjugateGradient(int maxIterations, double delta, boolean check)	Creates a new instance of this class, with default stopping criterion.
ConjugateGradient(IterationManager manager, double delta, boolean check)	Creates a new instance of this class, with default stopping criterion and custom iteration manager.

Method Summary

Modifier and Type	Method	Description
boolean	shouldCheck()	Returns true if positive-definiteness should be checked for both matrix and preconditioner.
RealVector	solveInPlace(RealLinearOperator a, RealLinearOperator m, RealVector b, RealVector x0)	Returns an estimate of the solution to the linear system A · x = b.

Methods inherited from class org.hipparchus.linear.PreconditionedIterativeLinearSolver

checkParameters, solve, solve, solve, solve, solveInPlace

Methods inherited from class org.hipparchus.linear.IterativeLinearSolver

checkParameters, getIterationManager

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

OPERATOR

public static final String OPERATOR

Key for the exception context.

See Also:

Constant Field Values

VECTOR

public static final String VECTOR

Key for the exception context.

See Also:

Constant Field Values

Constructor Detail

ConjugateGradient

public ConjugateGradient(int maxIterations,
                         double delta,
                         boolean check)

Creates a new instance of this class, with default stopping criterion.

Parameters:

maxIterations - the maximum number of iterations

delta - the δ parameter for the default stopping criterion

check - true if positive definiteness of both matrix and preconditioner should be checked

ConjugateGradient

public ConjugateGradient(IterationManager manager,
                         double delta,
                         boolean check)
                  throws NullArgumentException

Creates a new instance of this class, with default stopping criterion and custom iteration manager.

Parameters:

manager - the custom iteration manager

delta - the δ parameter for the default stopping criterion

check - true if positive definiteness of both matrix and preconditioner should be checked

Throws:

NullArgumentException - if manager is null

Method Detail

shouldCheck

public final boolean shouldCheck()

Returns true if positive-definiteness should be checked for both matrix and preconditioner.

Returns:

true if the tests are to be performed

Since:

1.4

solveInPlace

public RealVector solveInPlace(RealLinearOperator a,
                               RealLinearOperator m,
                               RealVector b,
                               RealVector x0)
                        throws MathIllegalArgumentException,
                               NullArgumentException,
                               MathIllegalStateException

Returns an estimate of the solution to the linear system A · x = b. The solution is computed in-place (initial guess is modified).

Specified by:

solveInPlace in class PreconditionedIterativeLinearSolver

Parameters:

a - the linear operator A of the system

m - the preconditioner, M (can be null)

b - the right-hand side vector

x0 - the initial guess of the solution

Returns:

a reference to x0 (shallow copy) updated with the solution

Throws:

MathIllegalArgumentException - if a or m is not positive definite

NullArgumentException - if one of the parameters is null

MathIllegalStateException - at exhaustion of the iteration count, unless a custom callback has been set at construction of the IterationManager