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:

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

Nested Classes

Modifier and Type	Class and 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 and Description
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

Constructors

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

Method Summary

Modifier and Type	Method and 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 Detail

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

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

FIRST_HOUSEHOLDER

public static final int FIRST_HOUSEHOLDER

Indicates the first Householder 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

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

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

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

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

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

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.