IMSL C# Numerical Library

GenMinRes Class

Linear system solver using the restarted Generalized Minimum Residual (GMRES) method.

For a list of all members of this type, see GenMinRes Members.

System.Object
   Imsl.Math.GenMinRes

public class GenMinRes

Thread Safety

Public static (Shared in Visual Basic) members of this type are safe for multithreaded operations. Instance members are not guaranteed to be thread-safe.

Remarks

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 property Method. 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.

Requirements

Namespace: Imsl.Math

Assembly: ImslCS (in ImslCS.dll)

See Also

GenMinRes Members | Imsl.Math Namespace | 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