43.2.2 Types of Sparse Iterative Solvers

The sparse linear algebra library provides the following types of iterative solvers:

Sparse Iterative Type: gsl_splinalg_itersolve_gmres

This specifies the Generalized Minimum Residual Method (GMRES). This is a projection method using {\cal K} = {\cal K}_m and {\cal L} = A {\cal K}_m where {\cal K}_m is the m-th Krylov subspace

K_m = span( r_0, A r_0, ..., A^(m-1) r_0)

and r_0 = b - A x_0 is the residual vector of the initial guess x_0. If m is set equal to n, then the Krylov subspace is {\bf R}^n and GMRES will provide the exact solution x. However, the goal is for the method to arrive at a very good approximation to x using a much smaller subspace {\cal K}_m. By default, the GMRES method selects m = MIN(n,10) but the user may specify a different value for m. The GMRES storage requirements grow as O(n(m+1)) and the number of flops grow as O(4 m^2 n - 4 m^3 / 3).

In the below function gsl_splinalg_itersolve_iterate, one GMRES iteration is defined as projecting the approximate solution vector onto each Krylov subspace {\cal K}_1, ..., {\cal K}_m, and so m can be kept smaller by "restarting" the method and calling gsl_splinalg_itersolve_iterate multiple times, providing the updated approximation x to each new call. If the method is not adequately converging, the user may try increasing the parameter m.

GMRES is considered a robust general purpose iterative solver, however there are cases where the method stagnates if the matrix is not positive-definite and fails to reduce the residual until the very last projection onto the subspace {\cal K}_n = {\bf R}^n. In these cases, preconditioning the linear system can help, but GSL does not currently provide any preconditioners.