Class ConjugateGradientNormalResidualSolver
- java.lang.Object
-
- dev.nm.algebra.linear.matrix.doubles.matrixtype.sparse.solver.iterative.nonstationary.ConjugateGradientNormalResidualSolver
-
- All Implemented Interfaces:
IterativeLinearSystemSolver
public class ConjugateGradientNormalResidualSolver extends 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 Residual method (CGNR) applies the Conjugate Gradient method (CG) to the normal equation(AtA)x = Atb
The equivalent symmetric system has the form: \[ \begin{bmatrix} 0 & A\\ A' & 0 \end{bmatrix} \times \begin{bmatrix} Ax\\ x \end{bmatrix} = \begin{bmatrix} b\\ A'b \end{bmatrix} \] 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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface dev.nm.algebra.linear.matrix.doubles.matrixtype.sparse.solver.iterative.IterativeLinearSystemSolver
IterativeLinearSystemSolver.Solution
-
-
Field Summary
Fields Modifier and Type Field Description static int
DEFAULT_RESIDUAL_REFRESH_RATE
The algorithm recomputes the residual as b - Axi once per this number of iterations
-
Constructor Summary
Constructors Constructor Description ConjugateGradientNormalResidualSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Residual method (CGNR) solver.ConjugateGradientNormalResidualSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Residual method (CGNR) solver.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.
-
-
-
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- See Also:
- Constant Field Values
-
-
Constructor Detail
-
ConjugateGradientNormalResidualSolver
public ConjugateGradientNormalResidualSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Residual method (CGNR) solver.- Parameters:
leftPreconditionerFactory
- constructs a new left preconditionerresidualRefreshRate
- the number of iterations before the next refreshmaxIteration
- the maximum number of iterationstolerance
- the convergence threshold
-
ConjugateGradientNormalResidualSolver
public ConjugateGradientNormalResidualSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Normal Residual method (CGNR) solver.- Parameters:
maxIteration
- the maximum number of iterationstolerance
- 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 iterativelyAx = 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 interfaceIterativeLinearSystemSolver
- Parameters:
problem
- a system of linear equationsmonitor
- an iteration monitor- Returns:
- an (approximate) solution to the linear problem
- Throws:
ConvergenceFailure
- if the algorithm fails to converge
-
-