How to establish that an iterative method for large linear systems is convergent in practice?

Question

In computational science we often encounter large linear systems which we are required to solve by some (efficient) means, e.g. by either direct or iterative methods. If we focus on the latter, how can we establish that an iterative method for solving a large linear systems is convergent in practice?

It is clear that we can do trial and error analysis (cf. Why is my iterative linear solver not converging?) and rely on iterative methods which guarantee convergence by proofs or have a sound experience base (e.g. Krylov subspace methods such as CG and GMRES for symmetric and nonsymmetric systems respectively).

But, what can be done to establish convergence in practice? and what is done?

Answer 1

For many partial differential equations arising in nature, particularly with strong nonlinearities or anisotropies, the choice of an appropriate preconditioner can have a large effect on whether the iterative method converges rapidly, slowly, or not at all. Examples of problems that are known to have fast and effective preconditioners include strongly elliptic partial differential equations, where the multigrid method frequently achieves rapid convergence. There are a number of tests one can use to assess convergence; here I am going to use the functionality from PETSc as an example, as it is arguably the oldest and most mature library for iteratively solving sparse systems of linear (and nonlinear equations).

PETSc uses an object called a KSPMonitor for monitoring the progress of an iterative solver, and deciding if the solver has converged or diverged. The monitor uses four different criterion to decide whether to halt. More details on the discussion here can be found in the man page for KSPGetConvergedReason().

We assume notationally the user is solving the following system of equations for $x$: $$Ax=b$$
We call the current guess $\hat{x}$, and define the residual $\hat{r}$ based on the style of preconditioning:

1. Left Preconditioning $\left(P^{-1}(Ax − b) \right)$ $$\hat{r}=P^{-1}(A\hat{x}-b)$$

2. No/Right Preconditioning $\left(AP^{-1}Px = b \right)$ $$\hat{r}=A\hat{x}-b$$

Convergence Criteria

1. Absolute Tolerance - The absolute tolerance criterion is satisfied when the norm of the residual is less than the predefined constant $a_{tol}$: $$\|\hat{r}\| \le a_{tol}$$
2. Relative Tolerance - The relative tolerance criterion is satisfied when the norm of the residual is less than the norm of the right hand side by a factor of predefined constant $r_{tol}$: $$\|\hat{r}\| \le r_{tol}\cdot \|b\|$$
3. Other Criteria - The iterative solve can also converge due to detection of a small step length or negative curvature.

Divergence Criteria

1. Maximum Iterations - The number of iterations a solver can take is capped by maximum iterations. If none of the other criteria has been met when the maximum number of iterations is reached, the monitor returns as diverged.

2. Residual NaN - If at any point the residual evaluates to NaN, the solver returns as diverged.

3. Divergence of Residual Norm The monitor returns as diverged if at any point the norm of the residual is greater than the norm of the right-hand side by a factor of predefined constant $d_{tol}$: $$\|\hat{r}\| \ge d_{tol}\cdot \|b\|$$

4. Solver Breakdown The Krylov method itself can signal divergence if it detects a singular matrix or preconditioner.