org.apache.commons.math3.linear
Class ConjugateGradient

java.lang.Object
  extended by org.apache.commons.math3.linear.IterativeLinearSolver
      extended by org.apache.commons.math3.linear.PreconditionedIterativeLinearSolver
          extended by org.apache.commons.math3.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 DimensionMismatchException, this class might throw NonPositiveDefiniteOperatorException if the linear operator or the preconditioner are not positive definite. In this case, the ExceptionContext provides some more information

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

Since:
3.0
Version:
$Id: ConjugateGradient.java 1244107 2012-02-14 16:17:55Z erans $

Field Summary
private  boolean check
          true if positive-definiteness of matrix and preconditioner should be checked.
private  double delta
          The value of δ, for the default stopping criterion.
static String OPERATOR
          Key for the exception context.
static String VECTOR
          Key for the exception context.
 
Constructor Summary
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
 boolean getCheck()
          Returns true if positive-definiteness should be checked for both matrix and preconditioner.
 RealVector solveInPlace(RealLinearOperator a, RealLinearOperator minv, RealVector b, RealVector x0)
          Returns an estimate of the solution to the linear system A · x = b.
 
Methods inherited from class org.apache.commons.math3.linear.PreconditionedIterativeLinearSolver
checkParameters, solve, solve, solve, solve, solveInPlace
 
Methods inherited from class org.apache.commons.math3.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

check

private boolean check
true if positive-definiteness of matrix and preconditioner should be checked.


delta

private final double delta
The value of δ, for the default stopping criterion.

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)
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
Method Detail

getCheck

public final boolean getCheck()
Returns true if positive-definiteness should be checked for both matrix and preconditioner.

Returns:
true if the tests are to be performed

solveInPlace

public RealVector solveInPlace(RealLinearOperator a,
                               RealLinearOperator minv,
                               RealVector b,
                               RealVector x0)
                        throws NullArgumentException,
                               NonSquareOperatorException,
                               DimensionMismatchException,
                               MaxCountExceededException
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
minv - the inverse of the preconditioner, M-1 (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:
NullArgumentException - if one of the parameters is null
NonSquareOperatorException - if a or minv is not square
DimensionMismatchException - if minv, b or x0 have dimensions inconsistent with a
MaxCountExceededException - at exhaustion of the iteration count, unless a custom callback has been set at construction.


Copyright (c) 2003-2013 Apache Software Foundation