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.
CG relies on symmetry to get a short recurrence. GMRES works without symmetry by explicitly building an orthonormal Krylov basis and choosing the vector in that subspace with smallest residual. This makes GMRES broadly applicable, but more expensive in memory.
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.
Arnoldi is the nonsymmetric analog of the Lanczos process. Each step applies \(\bA\) to the newest basis vector, then orthogonalizes the result against all previous basis vectors. The need to remember all previous basis vectors is the source of GMRES memory growth.
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\).
Let \(\br_0=\bb-\bA\bx_0\) and choose \(\bv_1=\br_0/\|\br_0\|_2\), so \(\br_0=\beta V_{k+1}\be_1\). If \(\bx_k=\bx_0+V_k\by\), then \[
\begin{align}
\br_k
&= \bb-\bA(\bx_0+V_k\by) \\
&= \br_0-\bA V_k\by \\
&= V_{k+1}\left(\beta\be_1-\bar{H}_k\by\right),
\end{align}
\] using the Arnoldi relation \(\bA V_k=V_{k+1}\bar{H}_k\). Since \(V_{k+1}\) has orthonormal columns, it preserves the Euclidean norm, giving \[
\begin{align}
\|\br_k\|_2=\|\beta\be_1-\bar{H}_k\by\|_2.
\end{align}
\]
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.
(Restart trade-off) GMRES(\(m\)) discards the Krylov basis every \(m\) steps and starts again from the current residual. This controls memory, but it also discards spectral information. Small restart values can cause long plateaus in convergence.
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}
\]
(Convergence is less predictable than CG) For nonnormal matrices, eigenvalues alone may not explain GMRES behavior. The geometry of eigenvectors and transient growth can matter. In practice, preconditioning is usually essential.
(Breakdown and stagnation) Arnoldi breakdown can be good: if the Krylov subspace becomes invariant and the residual reaches zero, GMRES has found the exact solution. Stagnation is different: the method keeps iterating but the residual barely decreases, often because the restart length or preconditioner is poor.
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\).