The Generalized Minimal Residual (GMRES) method is the standard Krylov subspace solver for general (non-symmetric) linear systems \(\bA\bx = \bb\). Unlike CG, it does not require \(\bA\) to be symmetric or positive definite.
Residual Minimization and Krylov Subspaces
The Minimization Problem: At each step \(k\), GMRES finds the approximate solution \(\bx_k\) in the affine space \(\bx_0 + \mathcal{K}_k(\bA, \br_0)\) that minimizes the Euclidean norm of the residual: \[
\begin{align}
\bx_k = \arg\min_{\bx \in \bx_0 + \mathcal{K}_k} \|\bb - \bA\bx\|_2.
\end{align}
\] Because the residual norm is minimized explicitly, it is guaranteed to be non-increasing with \(k\).
The Arnoldi Process
Basis Construction: To compute this minimum efficiently, GMRES uses the Arnoldi process to build an orthonormal basis \(V_k = [\bv_1, \bv_2, ..., \bv_k]\) for \(\mathcal{K}_k\). This process is essentially a Gram-Schmidt orthogonalization of the Krylov sequence.
The \(k\) steps of the Arnoldi process yield the fundamental relation: \[
\begin{align}
\bA V_k = V_{k+1} \bar{H}_k,
\end{align}
\] where \(\bar{H}_k\) is an \((k+1) \times k\) upper Hessenberg matrix. This relation expresses the action of \(\bA\) on the basis \(V_k\) in terms of the expanded basis \(V_{k+1}\).
Reduction to Hessenberg Least Squares
The critical insight of GMRES is that the \(n\)-dimensional residual minimization problem can be projected onto the \(k\)-dimensional Krylov subspace, resulting in a much smaller problem.
Let \(\bx_k = \bx_0 + V_k \by\) for some \(\by \in \fR^k\). The residual norm satisfies: \[
\begin{align}
\|\br_k\|_2 = \|\beta \be_1 - \bar{H}_k \by\|_2,
\end{align}
\] where \(\beta = \|\br_0\|_2\) and \(\be_1\) is the first canonical basis vector. Solving the original problem thus reduces to solving a \((k+1) \times k\) least-squares problem for \(\by\) using the small matrix \(\bar{H}_k\).
Optimality: By definition, GMRES finds the absolute best solution available in the growing Krylov subspace. The residual norm is non-increasing.
Restarted GMRES(\(m\))
The Memory Wall: Full GMRES storage costs \(O(kn)\) and work grows quadratically with \(k\) (due to orthogonalization). Restarting after \(m\) steps prevents memory explosion but can lead to stagnation.
Convergence and Preconditioning
\[
\begin{align}
\frac{\|\br_k\|_2}{\|\br_0\|_2} \leq \min_{p \in \mathcal{P}_k, p(0)=1} \max_{\lambda \in \sigma(\bA)} |p(\lambda)|.
\end{align}
\]
GMRES vs. CG: Compare residual plots for a symmetric system. Why is CG usually faster?
Restarting: Test GMRES(\(m\)) on a non-symmetric system for \(m=5, 20, 50\). Observe how small \(m\) can cause ``plateaus’’ in convergence.
Arnoldi: Implement the Arnoldi process via Modified Gram-Schmidt. Verify the Hessenberg structure of \(H_k = V_k^T \bA V_k\).