SuanShu, a Java numerical and statistical library

java.lang.Object
All Implemented Interfaces:
IterativeLinearSystemSolver

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 AAt 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

(AAt)y = b
for y, and then computes the solution
x = Aty
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 AAt will be less favorable than the spectrum of A.

Only left preconditioning is supported in this implementation.

"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
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 - Axi once per this number of iterations

Constant Field Values
Constructor Detail

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

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

SuanShu, a Java numerical and statistical library