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

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

All Implemented Interfaces:

IterativeLinearSystemSolver

public class ConjugateGradientSquaredSolver
extends java.lang.Object
implements IterativeLinearSystemSolver

The Conjugate Gradient Squared method (CGS) is useful for solving a non-symmetric n-by-n linear system. This method is a variant of BiCG that applies the updating operations for the A-sequence and the A^t-sequence both to the same vectors. Ideally, this would double the convergence rate, but in practice convergence may be much more irregular than for BiCG. This may sometimes lead to unreliable results. A practical advantage is that the CGS method does not need the multiplications with the transpose of the coefficient matrix. In some applications of CG methods, A is available only through some approximations but not explicitly. In such situations, the transpose of A, i.e., A^t, is usually not available. In addition, the rounding errors in the CGS method tend to be more damaging than in the standard BiCG algorithm.

Only left preconditioning is supported in this implementation.

See Also:

"Yousef Saad, “Conjugate Gradient Squared,” in Iterative Methods for Sparse Linear Systems, 2nd ed. 2000, ch. 7, sec. 7.4.1, p. 215-216."

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

ConjugateGradientSquaredSolver(int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Squared (CGS) solver.

ConjugateGradientSquaredSolver(PreconditionerFactory leftPreconditionerFactory, int residualRefreshRate, int maxIteration, Tolerance tolerance)
Construct a Conjugate Gradient Squared (CGS) 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

ConjugateGradientSquaredSolver

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

Construct a Conjugate Gradient Squared (CGS) 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

ConjugateGradientSquaredSolver

public ConjugateGradientSquaredSolver(int maxIteration,
                                      Tolerance tolerance)

Construct a Conjugate Gradient Squared (CGS) 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