## File: Sparse-Iterative-Solvers-Types.html

package info (click to toggle)
gsl-ref-html 2.3-1
• area: non-free
• in suites: bullseye, buster, sid
• size: 6,876 kB
• ctags: 4,574
• sloc: makefile: 35
 file content (122 lines) | stat: -rw-r--r-- 6,606 bytes parent folder | download
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122  GNU Scientific Library – Reference Manual: Sparse Iterative Solvers Types

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.