GMRES Algorithm - A Classical Iterative Method for Sparse Linear Systems

GMRES (Generalized Minimal Residual Method) is an iterative algorithm in numerical computation used for solving large sparse linear systems. It is particularly suitable for problems where the coefficient matrix is non-symmetric and doesn't satisfy specific conditions - such problems are often difficult to handle efficiently using traditional direct methods.

The core concept of GMRES involves iterative approximation of the solution through Krylov subspace methods. During each iteration, the algorithm searches for the solution that minimizes the residual within the current Krylov subspace. This process utilizes Arnoldi iteration to construct orthogonal bases, followed by least squares optimization to improve solution quality within this basis. In code implementation, this typically involves building an orthonormal basis using modified Gram-Schmidt orthogonalization and solving a small least-squares problem using QR decomposition.

Since GMRES requires storing all previously generated basis vectors, memory consumption increases with the number of iterations. To address this, restart strategies (GMRES(m)) are commonly implemented, where the algorithm restarts after a fixed number of iterations to control memory usage. However, this approach may sacrifice some convergence speed. Programmers often implement this using a while-loop structure with periodic reinitialization of the Krylov subspace basis.

The advantage of GMRES lies in its broad applicability, making it particularly suitable for handling linear systems in large-scale engineering and scientific computations. However, its convergence rate depends on the spectral distribution of the matrix, and in some cases may require combination with preconditioning techniques to accelerate convergence. Common preconditioning implementations include incomplete LU factorization or Jacobi preconditioning applied before the main GMRES iteration loop.