com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.nonstationary
Class ConjugateGradientNormalErrorSolver

java.lang.Object
  com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.nonstationary.ConjugateGradientNormalErrorSolver

All Implemented Interfaces:

IterativeLinearSystemSolver

public class ConjugateGradientNormalErrorSolver
extends java.lang.Object
implements IterativeLinearSystemSolver

For an under-determined system of linear equations, Ax = b, or when the coefficient matrix A is non-symmetric and nonsingular, the normal equation matrix AA^t is symmetric and positive definite, and hence CG is applicable. Thus, the Conjugate Gradient Normal Error method (CGNE) applies the Conjugate Gradient method (CG) to the normal equation

(AA^t)y = b

for y, and then computes the solution

x = A^ty

The equivalent symmetric system has the form: \[ \begin{bmatrix} I & A\\ A' & 0 \end{bmatrix} \times \begin{bmatrix} r\\ x \end{bmatrix} = \begin{bmatrix} b\\ 0 \end{bmatrix} \] with r = b - Ax arising from the standard necessary conditions satisfied by the solution of the constrained optimization problem, \[ \min \left \| r - b \right \|^2 \textup{ s.t., } A'r = 0 \] The convergence may be slow as the spectrum of AA^t will be less favorable than the spectrum of A.

Only left preconditioning is supported in this implementation.

See Also:

"Yousef Saad, "Preconditioned CG for the Normal Equations," in Iterative Methods for Sparse Linear Systems, 2nd ed. 2000, ch. 9, sec. 9.5, p. 259-260."

Nested Class Summary

Nested classes/interfaces inherited from interface com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.IterativeLinearSystemSolver

IterativeLinearSystemSolver.Solution

Field Summary

static int

DEFAULT_RESIDUAL_REFRESH_RATE The algorithm recomputes the residual as b - Axi once per this number of iterations

Constructor Summary

ConjugateGradientNormalErrorSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Error (CGNE) solver.

ConjugateGradientNormalErrorSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Error (CGNE) solver.

Method Summary

IterativeLinearSystemSolver.Solution	solve(LSProblem problem)
IterativeLinearSystemSolver.Solution	solve(LSProblem problem, IterationMonitor<Vector> monitor) Solves iteratively Ax = b until the solution converges, i.e., the norm of residual (b - Ax) is less than or equal to the threshold.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_RESIDUAL_REFRESH_RATE

public static final int DEFAULT_RESIDUAL_REFRESH_RATE

The algorithm recomputes the residual as b - Ax_i once per this number of iterations

See Also:

Constant Field Values

Constructor Detail

ConjugateGradientNormalErrorSolver

public ConjugateGradientNormalErrorSolver(PreconditionerFactory leftPreconditionerFactory,
                                          int residualRefreshRate,
                                          int maxIteration,
                                          Tolerance tolerance)

Construct a Conjugate Gradient Normal Error (CGNE) solver.

Parameters:

leftPreconditionerFactory - constructs a new left preconditioner

residualRefreshRate - the number of iterations before the next refresh

maxIteration - the maximum number of iterations

tolerance - the convergence threshold

ConjugateGradientNormalErrorSolver

public ConjugateGradientNormalErrorSolver(int maxIteration,
                                          Tolerance tolerance)

Construct a Conjugate Gradient Normal Error (CGNE) solver.

Parameters:

maxIteration - the maximum number of iterations

tolerance - the convergence threshold

Method Detail

solve

public IterativeLinearSystemSolver.Solution solve(LSProblem problem)
                                           throws ConvergenceFailure

Throws:

ConvergenceFailure

solve

public IterativeLinearSystemSolver.Solution solve(LSProblem problem,
                                                  IterationMonitor<Vector> monitor)
                                           throws ConvergenceFailure

Description copied from interface: IterativeLinearSystemSolver

Solves iteratively

Ax = b

until the solution converges, i.e., the norm of residual (b - Ax) is less than or equal to the threshold.

Specified by:

solve in interface IterativeLinearSystemSolver

Parameters:

problem - a system of linear equations

monitor - an iteration monitor

Returns:

an (approximate) solution to the linear problem

Throws:

ConvergenceFailure - if the algorithm fails to converge