JMSLTM Numerical Library 6.1

com.imsl.math
Class GenMinRes

java.lang.Object
  extended by 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,Anu,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:
Simple Example, Simple Example with User Supplied Inner Product, Sparse Example, Sparse Example with Preconditioning, Second Householder Implementation Example, Second Householder Implementation Example with Preconditioning, Simple Example with Logging, Serialized Form

Nested Class Summary
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
static int DIRECT_AT_RESTART_AND_TERMINATION
          Indicates residual updating is to be done by direct evaluation upon restarting and at termination.
static int DIRECT_AT_RESTART_ONLY
          Indicates residual updating is to be done by direct evaluation upon restarting only.
static int FIRST_GRAM_SCHMIDT
          Indicates the first Gram-Schmidt implementation method is to be used.
static int FIRST_HOUSEHOLDER
          Indicates the first Householder implementation method is to be used.
static int LINEAR_AT_RESTART_AND_TERMINATION
          Indicates residual updating is to be done by linear combination upon restarting and at termination.
static int LINEAR_AT_RESTART_ONLY
          Indicates residual updating is to be done by linear combination upon restarting only.
static int SECOND_GRAM_SCHMIDT
          Indicates the second Gram-Schmidt implementation method is to be used.
static int SECOND_HOUSEHOLDER
          Indicates the second Householder implementation method is to be used.
 
Constructor Summary
GenMinRes(int n, GenMinRes.Function argF)
          GMRES linear system solver constructor.
 
Method Summary
 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 Detail

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:
Constant Field Values

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:
Constant Field Values

FIRST_GRAM_SCHMIDT

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

See Also:
Constant Field Values

FIRST_HOUSEHOLDER

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

See Also:
Constant Field Values

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:
Constant Field Values

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:
Constant Field Values

SECOND_GRAM_SCHMIDT

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

See Also:
Constant Field Values

SECOND_HOUSEHOLDER

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

See Also:
Constant Field Values
Constructor Detail

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 Detail

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.

getIterations

public int getIterations()
Returns the actual number of GMRES iterations used.

Returns:
an int scalar representing the number of iterations used.

getLogger

public Logger getLogger()
Returns the logger object.

Returns:
the logger object, if present, or null.

getMaxIterations

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

Returns:
an int specifying the maximum number of iterations allowed.

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.

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.

getPreconditionerSolves

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

Returns:
An int representing the number of GMRES right preconditioner solves.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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

JMSLTM Numerical Library 6.1

Copyright © 1970-2010 Visual Numerics, Inc.
Built July 30 2010.