Package com.imsl.math

Class GenMinRes

java.lang.Object
com.imsl.math.GenMinRes
All Implemented Interfaces:
Serializable
public class GenMinRes extends Object implements Serializable
Linear system solver using the restarted Generalized Minimum Residual (GMRES) method.

GenMinRes implements restarted GMRES to generate an approximate solution to \( Ax = b \). It is based on GMRES by Homer Walker (1988).

The GMRES method begins with an approximate solution \(x_0\) and an initial residual \(r_0 = b-Ax_0\). At iteration m, a correction \(z_m\) is determined in the Krylov subspace $$ {\kappa}_m (\nu)=\rm{span}(\nu,A\nu,\ldots,A^{m-1}\nu ) $$ \(\nu = r_0 \) which solves the least squares problem $$\min_{z \in \kappa_m(r_0)}{\Vert b-A(x_0 + z) \Vert}_2$$ Then at iteration m, \( x_m = x_0 + z_m \).

There are four distinct GMRES implementations, selectable through method setMethod. The first Gram-Schmidt implementation is essentially the original algorithm by Saad and Schultz (1986). The second Gram-Schmidt implementation, developed by Homer Walker and Lou Zhou, is simpler than the first implementation. The least squares problem is constructed in upper-triangular form and the residual vector updating at the end of a GMRES cycle is cheaper. The first Householder implementation is algorithm 2.2 of Walker (1988), but with more efficient correction accumulation at the end of each GMRES cycle. The second Householder implementation is algorithm 3.1 of Walker (1988). The products of Householder transformations are expanded as sums, allowing most work to be formulated as large scale matrix-vector operations.

The Gram-Schmidt implementations are less expensive than the Householder, the latter requiring about twice as many computations beyond the coefficient matrix/vector products. However, the Householder implementations may be more reliable near the limits of residual reduction. See Walker (1988) for details. Issues such as the cost of coefficient matrix/vector products, availability of effective preconditioners, and features of particular computing environments may serve to mitigate the extra expense of the Householder implementations.

Note that one can use the JAVA Logging API to generate intermediate output for the solver. Accumulated levels of detail correspond to JAVA's FINE and FINER logging levels with FINE yielding the smallest amount of information and FINER yielding the most. The levels of output yield the following:

Level Output
FINE A summary report is printed upon completion.
FINER Lines of intermediate results giving the most important data for each step are printed after each step. A summary report is printed upon completion.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    GenMinRes.Formatter
    Deprecated.
    Use IMSLFormatter instead.
    static interface 
    GenMinRes.Function
    Public interface for the user supplied function to GenMinRes.
    static interface 
    GenMinRes.Norm
    Public interface for the user supplied function to the GenMinRes object used for the norm \( \Vert X \Vert \) when the Gram-Schmidt implementation is used.
    static interface 
    GenMinRes.Preconditioner
    Public interface for the user supplied function to GenMinRes used for preconditioning.
    static class 
    GenMinRes.TooManyIterationsException
    Maximum number of iterations exceeded.
    static interface 
    GenMinRes.VectorProducts
    Public interface for the user supplied function to the GenMinRes object used for the inner product when the Gram-Schmidt implementation is used.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DIRECT_AT_RESTART_AND_TERMINATION
    Indicates residual updating is to be done by direct evaluation upon restarting and at termination.
    static final int
    DIRECT_AT_RESTART_ONLY
    Indicates residual updating is to be done by direct evaluation upon restarting only.
    static final int
    FIRST_GRAM_SCHMIDT
    Indicates the first Gram-Schmidt implementation method is to be used.
    static final int
    FIRST_HOUSEHOLDER
    Indicates the first Householder implementation method is to be used.
    static final int
    LINEAR_AT_RESTART_AND_TERMINATION
    Indicates residual updating is to be done by linear combination upon restarting and at termination.
    static final int
    LINEAR_AT_RESTART_ONLY
    Indicates residual updating is to be done by linear combination upon restarting only.
    static final int
    SECOND_GRAM_SCHMIDT
    Indicates the second Gram-Schmidt implementation method is to be used.
    static final int
    SECOND_HOUSEHOLDER
    Indicates the second Householder implementation method is to be used.

  • Constructor Summary

    Constructors
    Constructor
    Description
    GenMinRes(int n, GenMinRes.Function argF)
    GMRES linear system solver constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    double[]
    getGuess()
    Returns the initial guess of the solution.
    int
    getIterations()
    Returns the actual number of GMRES iterations used.
    Logger
    getLogger()
    Returns the logger object.
    int
    getMaxIterations()
    Returns the maximum number of iterations allowed.
    int
    getMaxKrylovDim()
    Returns the maximum Krylov subspace dimension, i.e., the maximum allowable number of GMRES iterations allowed before restarting.
    int
    getMethod()
    Returns the implementation method to be used.
    int
    getPreconditionerSolves()
    Returns the total number of GMRES right preconditioner solves.
    int
    getProducts()
    Returns the total number of GMRES matrix-vector products used.
    double
    getRelativeError()
    Returns the stopping tolerance.
    double
    getResidualNorm()
    Returns the final residual norm, \({\Vert b-Ax \Vert}_2\) .
    int
    getResidualUpdating()
    Returns the residual updating method to be used.
    GenMinRes.VectorProducts
    getVectorProducts()
    Returns the user-supplied functions for the inner product and, optionally, the norm used in the Gram-Schmidt implementations.
    void
    setGuess(double[] xguess)
    Set the initial guess of the solution.
    void
    setMaxIterations(int maxIterations)
    Set the maximum number of iterations allowed.
    void
    setMaxKrylovDim(int kdmax)
    Set the maximum Krylov subspace dimension, i.e., the maximum allowable number of GMRES iterations allowed before restarting.
    void
    setMethod(int iMethod)
    Set the implementation method to be used.
    void
    setRelativeError(double tolerance)
    Set the stopping tolerance.
    void
    setResidualUpdating(int rMethod)
    Set the residual updating method to be used.
    void
    setVectorProducts(GenMinRes.VectorProducts argP)
    Sets the user-supplied functions for the inner product and, optionally, the norm to be used in the Gram-Schmidt implementations.
    double[]
    solve(double[] b)
    Generate an approximate solution to \(Ax=b\) using the Generalized Residual Method.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • FIRST_GRAM_SCHMIDT

      public static final int FIRST_GRAM_SCHMIDT
      Indicates the first Gram-Schmidt implementation method is to be used.
      See Also:

    • SECOND_GRAM_SCHMIDT

      public static final int SECOND_GRAM_SCHMIDT
      Indicates the second Gram-Schmidt implementation method is to be used.
      See Also:

    • FIRST_HOUSEHOLDER

      public static final int FIRST_HOUSEHOLDER
      Indicates the first Householder implementation method is to be used.
      See Also:

    • SECOND_HOUSEHOLDER

      public static final int SECOND_HOUSEHOLDER
      Indicates the second Householder implementation method is to be used.
      See Also:

    • LINEAR_AT_RESTART_ONLY

      public static final int LINEAR_AT_RESTART_ONLY
      Indicates residual updating is to be done by linear combination upon restarting only.
      See Also:

    • LINEAR_AT_RESTART_AND_TERMINATION

      public static final int LINEAR_AT_RESTART_AND_TERMINATION
      Indicates residual updating is to be done by linear combination upon restarting and at termination.
      See Also:

    • DIRECT_AT_RESTART_ONLY

      public static final int DIRECT_AT_RESTART_ONLY
      Indicates residual updating is to be done by direct evaluation upon restarting only.
      See Also:

    • DIRECT_AT_RESTART_AND_TERMINATION

      public static final int DIRECT_AT_RESTART_AND_TERMINATION
      Indicates residual updating is to be done by direct evaluation upon restarting and at termination.
      See Also:

  • Constructor Details

    • GenMinRes

      public GenMinRes(int n, GenMinRes.Function argF)
      GMRES linear system solver constructor.
      Parameters:
      n - An int scalar value which defines the order of the system to be solved
      argF - a Function that defines the user-supplied function which computes \( z = Ap \). If argF implements Preconditioner then right preconditioning is performed using this user supplied function. Otherwise, no preconditioning is performed. Note that argF can be used to act upon the coefficients of matrix A stored in different storage modes. See the examples.

  • Method Details

    • solve

      public double[] solve(double[] b) throws SingularMatrixException, GenMinRes.TooManyIterationsException
      Generate an approximate solution to \(Ax=b\) using the Generalized Residual Method.
      Parameters:
      b - a double array which defines the right-hand side of the linear system.
      Returns:
      a double array containing the solution of the linear system.
      Throws:
      IllegalArgumentException - is thrown if if the length of b is not consistent with n.
      SingularMatrixException
      GenMinRes.TooManyIterationsException

    • setGuess

      public void setGuess(double[] xguess)
      Set the initial guess of the solution. If this member function is not called, the elements of this array are set to 0.0.
      Parameters:
      xguess - a double array of length n specifying the initial guess of the solution.

    • getGuess

      public double[] getGuess()
      Returns the initial guess of the solution.
      Returns:
      a double array of length n containing the initial guess of the solution.

    • setRelativeError

      public void setRelativeError(double tolerance)
      Set the stopping tolerance. The algorithm attempts to generate x such that \({\Vert b-Ax \Vert}_2 \le t {\Vert b \Vert}_2\), where t = tolerance. If this member function is not called, tolerance is set to 1.4901161193847656e-08.
      Parameters:
      tolerance - a double scalar value specifying the stopping tolerance. By default, tolerance = 1.49e-08.
      Throws:
      IllegalArgumentException - is thrown if tolerance is less than or equal to 0.0

    • getRelativeError

      public double getRelativeError()
      Returns the stopping tolerance. The algorithm attempts to generate x such that \({\Vert b-Ax \Vert}_2 \le t {\Vert b \Vert}_2\), where t = tolerance.
      Returns:
      a double scalar value specifying the stopping tolerance.

    • getResidualNorm

      public double getResidualNorm()
      Returns the final residual norm, \({\Vert b-Ax \Vert}_2\) .
      Returns:
      a double scalar value specifying the final residual norm.

    • setMaxKrylovDim

      public void setMaxKrylovDim(int kdmax)
      Set the maximum Krylov subspace dimension, i.e., the maximum allowable number of GMRES iterations allowed before restarting. If this member function is not called, kdmax is set to the minimum of n and 20.
      Throws:
      IllegalArgumentException - is thrown if kdmax is less than 1 or greater than n.

    • getMaxKrylovDim

      public int getMaxKrylovDim()
      Returns the maximum Krylov subspace dimension, i.e., the maximum allowable number of GMRES iterations allowed before restarting.
      Returns:
      An int scalar representing the maximum Krylov subspace dimension, i.e., the maximum allowable number of GMRES iterations allowed before restarting.

    • setMethod

      public void setMethod(int iMethod)
      Set the implementation method to be used.
      Parameters:
      iMethod - an int scalar value specifying the implementation method to be used. If this member function is not called, iMethod is set to FIRST_GRAM_SCHMIDT.
      iMethod Description
      FIRST_GRAM_SCHMIDT Use the first Gram-Schmidt implementation. This is the default value used.
      SECOND_GRAM_SCHMIDT Use the second Gram-Schmidt implementation.
      FIRST_HOUSEHOLDER Use the first Householder implementation.
      SECOND_HOUSEHOLDER Use the second Householder implementation.
      Throws:
      IllegalArgumentException - is thrown if iMethod is less than 1 or greater than 4.

    • getMethod

      public int getMethod()
      Returns the implementation method to be used.
      Returns:
      an int scalar value specifying the implementation method to be used.
      Return Value Method
      1 = FIRST_GRAM_SCHMIDT Use the first Gram-Schmidt implementation. This is the default value used.
      2 = SECOND_GRAM_SCHMIDT Use the second Gram-Schmidt implementation.
      3 = FIRST_HOUSEHOLDER Use the first Householder implementation.
      4 = SECOND_HOUSEHOLDER Use the second Householder implementation.

    • setResidualUpdating

      public void setResidualUpdating(int rMethod)
      Set the residual updating method to be used.
      Parameters:
      rMethod - an int scalar value specifying the residual updating method to be used. If this member function is not called, rMethod is set to LINEAR_AT_RESTART_ONLY.
      rMethod Description
      LINEAR_AT_RESTART_ONLY Update by linear combination upon restarting only. This is the default value used.
      LINEAR_AT_RESTART_AND_TERMINATION Update by linear combination upon restarting and at termination.
      DIRECT_AT_RESTART_ONLY Update by direct evaluation upon restarting only.
      DIRECT_AT_RESTART_AND_TERMINATION Update by direct evaluation upon restarting and at termination.
      Throws:
      IllegalArgumentException - is thrown if rMethod is less than 1 or greater than 4.

    • getResidualUpdating

      public int getResidualUpdating()
      Returns the residual updating method to be used.
      Returns:
      an int scalar value specifying the residual updating method to be used.
      Return Value Method
      1 = LINEAR_AT_RESTART_ONLY Update by linear combination upon restarting only. This is the default value used.
      2 = LINEAR_AT_RESTART_AND_TERMINATION Update by linear combination upon restarting and at termination.
      3 = DIRECT_AT_RESTART_ONLY Update by direct evaluation upon restarting only.
      4 = DIRECT_AT_RESTART_AND_TERMINATION Update by direct evaluation upon restarting and at termination.

    • getIterations

      public int getIterations()
      Returns the actual number of GMRES iterations used.
      Returns:
      an int scalar representing the number of iterations used.

    • getProducts

      public int getProducts()
      Returns the total number of GMRES matrix-vector products used.
      Returns:
      An int representing the number of GMRES matrix-vector products used.

    • getPreconditionerSolves

      public int getPreconditionerSolves()
      Returns the total number of GMRES right preconditioner solves.
      Returns:
      An int representing the number of GMRES right preconditioner solves.

    • setMaxIterations

      public void setMaxIterations(int maxIterations)
      Set the maximum number of iterations allowed.
      Parameters:
      maxIterations - an int specifying the maximum number of iterations allowed. By default, maxIterations = 1000.
      Throws:
      IllegalArgumentException - is thrown if maxIterations is less than or equal to 0.

    • getMaxIterations

      public int getMaxIterations()
      Returns the maximum number of iterations allowed.
      Returns:
      an int specifying the maximum number of iterations allowed.

    • setVectorProducts

      public void setVectorProducts(GenMinRes.VectorProducts argP)
      Sets the user-supplied functions for the inner product and, optionally, the norm to be used in the Gram-Schmidt implementations.
      Parameters:
      argP - a VectorProduct specifying the user-defined function for the inner product and, optionally, the norm in the Gram-Schmidt implementations. If this member function is not called, the dot product will be used for the inner product and the \( L_2 \) norm will be used for the norm.

    • getVectorProducts

      public GenMinRes.VectorProducts getVectorProducts()
      Returns the user-supplied functions for the inner product and, optionally, the norm used in the Gram-Schmidt implementations.
      Returns:
      a VectorProducts that defines the user-supplied functions for the inner product and, optionally, the norm used in the Gram-Schmidt implementations.

    • getLogger

      public Logger getLogger()
      Returns the logger object.
      Returns:
      the logger object, if present, or null.