Stopping Tests

The following stopping tests are permitted for the iterative methods. In each case, the iteration process stops whenever the given quantity falls below ZETA [= RPARM(1)]. The number given in parentheses is the corresponding value of NTEST [= IPARM(1)]. A large number of stopping tests is provided for experimentation by the user. See [20] for comments regarding the motivation in using these tests.

$$\frac{\mbox{EMAX}}{\mbox{EMIN}} \left[\frac {\langle r^{(n)},\tilde z^{(n)}\rangle} {\langle b,Q^{-1}b \rangle} \right]^\frac{1}{2} \zeta$$ < (1)

$$\frac{1}{\mbox{EMIN}} \left[\frac {\langle\tilde z^{(n)},\tilde z^{(n)}\rangle} {\langle u^{(n)},u^{(n)}\rangle} \right]^\frac{1}{2} \zeta$$ < (2)

$$\frac{\mbox{EMAX}}{\mbox{EMIN}} \left[\frac {\langle\tilde z^{(n)},\tilde z^{(n)}\rangle} {\langle Q^{-1}b,Q^{-1}b\rangle} \right]^\frac{1}{2} \zeta$$ < (3)

$$\left[\frac{\langle\tilde z^{(n)},\tilde z^{(n)}\rangle} {\langle Q^{-1}b,Q^{-1}b\rangle} \right]^\frac{1}{2} \zeta$$ < (4)

$$\left[\frac{\langle r^{(n)},r^{(n)}\rangle} {\langle b,b \rangle} \right]^\frac{1}{2} \zeta$$ < (5)

$$\left[\frac{\langle u^{(n)}-\bar{u},u^{(n)}-\bar{u} \rangle} {\langle\bar{u},\bar{u} \rangle} \right]^\frac{1}{2} \zeta$$ < (6)

$$\frac{\mbox{EMAX}}{\mbox{EMIN}} \left[\frac {\langle r^{(n)},z^{(n)}\rangle} {\langle b,Q_L^{-1}b \rangle} \right]^\frac{1}{2} \zeta$$ < (7)

$$\frac{1}{\mbox{EMIN}} \left[\frac {\langle z^{(n)},z^{(n)}\rangle} {\langle u^{(n)},u^{(n)}\rangle} \right]^\frac{1}{2} \zeta$$ < (8)

$$\frac{\mbox{EMAX}}{\mbox{EMIN}} \left[\frac {\langle z^{(n)},z^{(n)}\rangle} {\langle Q_L^{-1}b,Q_L^{-1}b\rangle} \right]^\frac{1}{2} \zeta$$ < (9)

$$\left[\frac{\langle z^{(n)},z^{(n)}\rangle} {\langle Q_L^{-1}b,Q_L^{-1}b\rangle} \right]^\frac{1}{2} \zeta$$ < (10)

Here, EMAX [= RPARM(2)] and EMIN [= RPARM(3)] are estimates of the 2-norm of the preconditioned matrix and its inverse. In the symmetric case, EMAX and EMIN are estimates of the maximum and minimum eigenvalues of Q^-1A, respectively. Also,

Q	is the preconditioning matrix,
u(n)	is the current iterate,
r(n)=b-Au(n)	is the current residual,
z(n)=QL-1r(n)	is the current left-preconditioned residual,
$\tilde z^{(n)}=Q^{-1}r^{(n)}=Q_R^{-1}Q_L^{-1}r^{(n)}$	is the current pseudo-residual, and
$\bar{u}=A^{-1}b$	is the true solution.

Various accelerators calculate certain vectors or inner products automatically, allowing the stopping test to be performed very cheaply. A judicious choice of stopping test is necessary in order to permit the accelerator to run most efficiently.

Stopping test (6) requires that UBAR contain the solution to Au=b. This stopping test may be used for testing purposes whenever the exact solution UBAR is known.

Tests for the Symmetric Accelerators

The symmetric accelerators CG, SI, SRCG, and SRSI can use any of the stopping tests efficiently and can adaptively obtain the EMAX and EMIN estimates if MAXADP [= IPARM(6)] and MINADP [= IPARM(7)] are set to one, respectively. Hence, stopping tests (1) through (3) are good choices. Also, the inner product $\langle r,\tilde{z} \rangle$ is already computed for these accelerators, making stopping test (1) very cheap to compute. If the user has estimates of EMAX or EMIN and wishes that these estimates be used in the stopping test, then RPARM(2) or RPARM(3) should be set to these estimates before calling NSPCG, and MAXADP or MINADP should be set to zero. The SOR routine uses a specialized stopping test:

$$\begin{eqnarray*}\frac{1}{1-{\rm SPECR}} \left[\frac {\langle u^{(n)}-u^{(n-1)}... ...\langle u^{(n)},u^{(n)}\rangle} \right] ^\frac{1}{2}& < & \zeta \end{eqnarray*}$$

where SPECR is an estimate of the spectral radius of the SOR matrix. SPECR is adaptively computed by the SOR accelerator. This stopping test and stopping test (6) are the only stopping tests available for the SOR algorithm. Also, the stopping criterion for SOR is initially set to a large value so that at least one Gauss-Seidel iteration is performed.

Tests for the Nonsymmetric Accelerators

The safest and most economical stopping test for the nonsymmetric accelerators is stopping test (10), based on the norm of the left-preconditioned residual. This calculation can usually be done cheaply. For most accelerators it requires at most one extra dot product per iteration, and in some cases (e.g. IOM, GMRES) the quantity is a by-product of the iterative algorithm and is available at no extra cost.

In some cases it is desirable to use a stopping criterion which bounds the relative error of the solution to the original problem. Stopping test (3) is designed to do this. It requires that the accelerator be able to estimate the extremal eigenvalues of the iteration matrix; this is presently available for the nonsymmetric accelerators CGNR, OMIN and CGCR. In the case of OMIN, the variable NS3 is used to denote the size of the largest Hessenberg matrix to be used to estimate the eigenvalues; a typical useful value is NS3=40.

However, if IQLR = 2 or 3 and a stopping test involving the right-preconditioned residual is employed (e.g. NTEST=3), the accelerator may have to do significant extra work to perform the stopping test. In this case the accelerators OMIN and LANMIN, for instance, require only one inner product per iteration. However, GMRES takes significant extra work per iteration if a right preconditioning matrix is present.