Class ConjugateGradientNormalErrorSolver

  • All Implemented Interfaces:
    IterativeLinearSystemSolver

    public class ConjugateGradientNormalErrorSolver
    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 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.

    • 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

      • 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