Class ConjugateGradientSolver
- java.lang.Object
-
- dev.nm.algebra.linear.matrix.doubles.matrixtype.sparse.solver.iterative.nonstationary.ConjugateGradientSolver
-
- All Implemented Interfaces:
IterativeLinearSystemSolver
public class ConjugateGradientSolver extends Object implements IterativeLinearSystemSolver
The Conjugate Gradient method (CG) is useful for solving a symmetric n-by-n linear system. The method derives its name from the fact that it generates a sequence of conjugate (or orthogonal) vectors. These vectors are the residuals of the iterates. They are also the gradients of a quadratic function, the minimization of which is equivalent to solving the linear system. CG is an extremely effective method when the coefficient matrix is symmetric positive definite as storage for only a limited number of vectors is required. For a coefficient matrix that is not symmetric, not positive-definite, and even not square, there are solvers using the CG method. For example, CGNR solves an over-determined system; CGNE solves an under-determined system. If A is symmetric, positive-definite and square, the CG method solvesAx = b
Note that if the coefficient matrix A passed into the algorithm is not symmetric positive-definite, the algorithm behaves unexpectedly. Only left preconditioning is supported in this implementation. The preconditioner must be symmetric and positive definite.
-
-
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 ConjugateGradientSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient (CG) solver.ConjugateGradientSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient (CG) 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
-
ConjugateGradientSolver
public ConjugateGradientSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient (CG) solver.- Parameters:
leftPreconditionerFactory
- constructs a new left preconditionerresidualRefreshRate
- the number of iterations before the next refreshmaxIteration
- the maximum number of iterationstolerance
- the convergence threshold
-
ConjugateGradientSolver
public ConjugateGradientSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient (CG) 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
-
-