Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sparse_real_gen_basic_setup (f11bd)

## Purpose

nag_sparse_real_gen_basic_setup (f11bd) is a setup function, the first in a suite of three functions for the iterative solution of a real general (nonsymmetric) system of simultaneous linear equations. nag_sparse_real_gen_basic_setup (f11bd) must be called before nag_sparse_real_gen_basic_solver (f11be), the iterative solver. The third function in the suite, nag_sparse_real_gen_basic_diag (f11bf), can be used to return additional information about the computation.
These three functions are suitable for the solution of large sparse general (nonsymmetric) systems of equations.

## Syntax

[lwreq, work, ifail] = f11bd(method, precon, n, m, tol, maxitn, anorm, sigmax, monit, lwork, 'norm_p', norm_p, 'weight', weight, 'iterm', iterm)
[lwreq, work, ifail] = nag_sparse_real_gen_basic_setup(method, precon, n, m, tol, maxitn, anorm, sigmax, monit, lwork, 'norm_p', norm_p, 'weight', weight, 'iterm', iterm)

## Description

The suite consisting of the functions nag_sparse_real_gen_basic_setup (f11bd), nag_sparse_real_gen_basic_solver (f11be) and nag_sparse_real_gen_basic_diag (f11bf) is designed to solve the general (nonsymmetric) system of simultaneous linear equations Ax = b$Ax=b$ of order n$n$, where n$n$ is large and the coefficient matrix A$A$ is sparse.
nag_sparse_real_gen_basic_setup (f11bd) is a setup function which must be called before nag_sparse_real_gen_basic_solver (f11be), the iterative solver. The third function in the suite, nag_sparse_real_gen_basic_diag (f11bf), can be used to return additional information about the computation. A choice of methods is available:
• restarted generalized minimum residual method (RGMRES);
• conjugate gradient squared method (CGS);
• bi-conjugate gradient stabilized ($\ell$) method (Bi-CGSTAB($\ell$));
• transpose-free quasi-minimal residual method (TFQMR).

### Restarted Generalized Minimum Residual Method (RGMRES)

The restarted generalized minimum residual method (RGMRES) (see Saad and Schultz (1986), Barrett et al. (1994) and Dias da Cunha and Hopkins (1994)) starts from the residual r0 = bAx0${r}_{0}=b-A{x}_{0}$, where x0${x}_{0}$ is an initial estimate for the solution (often x0 = 0${x}_{0}=0$). An orthogonal basis for the Krylov subspace span{Akr0}$\mathrm{span}\left\{{A}^{\mathit{k}}{r}_{0}\right\}$, for k = 0,1,$\mathit{k}=0,1,\dots$, is generated explicitly: this is referred to as Arnoldi's method (see Arnoldi (1951)). The solution is then expanded onto the orthogonal basis so as to minimize the residual norm bAx2${‖b-Ax‖}_{2}$. The lack of symmetry of A$A$ implies that the orthogonal basis is generated by applying a ‘long’ recurrence relation, whose length increases linearly with the iteration count. For all but the most trivial problems, computational and storage costs can quickly become prohibitive as the iteration count increases. RGMRES limits these costs by employing a restart strategy: every m$m$ iterations at most, the Arnoldi process is restarted from rl = bAxl${r}_{l}=b-A{x}_{l}$, where the subscript l$l$ denotes the last available iterate. Each group of m$m$ iterations is referred to as a ‘super-iteration’. The value of m$m$ is chosen in advance and is fixed throughout the computation. Unfortunately, an optimum value of m$m$ cannot easily be predicted.

### Conjugate Gradient Squared Method (CGS)

The conjugate gradient squared method (CGS) (see Sonneveld (1989), Barrett et al. (1994) and Dias da Cunha and Hopkins (1994)) is a development of the bi-conjugate gradient method where the nonsymmetric Lanczos method is applied to reduce the coefficients matrix to real tridiagonal form: two bi-orthogonal sequences of vectors are generated starting from the residual r0 = bAx0${r}_{0}=b-A{x}_{0}$, where x0${x}_{0}$ is an initial estimate for the solution (often x0 = 0${x}_{0}=0$) and from the shadow residual 0${\stackrel{^}{r}}_{0}$ corresponding to the arbitrary problem AT = ${A}^{\mathrm{T}}\stackrel{^}{x}=\stackrel{^}{b}$, where $\stackrel{^}{b}$ can be any vector, but in practice is chosen so that r0 = 0${r}_{0}={\stackrel{^}{r}}_{0}$. In the course of the iteration, the residual and shadow residual ri = Pi(A) r0${r}_{i}={P}_{i}\left(A\right){r}_{0}$ and i = Pi(AT) 0${\stackrel{^}{r}}_{i}={P}_{i}\left({A}^{\mathrm{T}}\right){\stackrel{^}{r}}_{0}$ are generated, where Pi${P}_{i}$ is a polynomial of order i$i$, and bi-orthogonality is exploited by computing the vector product ρi = (i,ri) = (Pi(AT)0, Pi(A) r0) = (0,Pi2(A) r0)${\rho }_{i}=\left({\stackrel{^}{r}}_{i},{r}_{i}\right)=\left({P}_{i}\left({A}^{\mathrm{T}}\right){\stackrel{^}{r}}_{0},{P}_{i}\left(A\right){r}_{0}\right)=\left({\stackrel{^}{r}}_{0},{P}_{i}^{2}\left(A\right){r}_{0}\right)$. Applying the ‘contraction’ operator Pi(A)${P}_{i}\left(A\right)$ twice, the iteration coefficients can still be recovered without advancing the solution of the shadow problem, which is of no interest. The CGS method often provides fast convergence; however, there is no reason why the contraction operator should also reduce the once reduced vector Pi(A)r0${P}_{i}\left(A\right){r}_{0}$: this may well lead to a highly irregular convergence which may result in large cancellation errors.

### Bi-Conjugate Gradient Stabilized (ℓ) Method (Bi-CGSTAB(ℓ))

The bi-conjugate gradient stabilized ($\ell$) method (Bi-CGSTAB($\ell$)) (see Van der Vorst (1989), Sleijpen and Fokkema (1993) and Dias da Cunha and Hopkins (1994)) is similar to the CGS method above. However, instead of generating the sequence {Pi2(A)r0}$\left\{{P}_{i}^{2}\left(A\right){r}_{0}\right\}$, it generates the sequence {Qi(A)Pi(A)r0}$\left\{{Q}_{i}\left(A\right){P}_{i}\left(A\right){r}_{0}\right\}$, where the Qi(A)${Q}_{i}\left(A\right)$ are polynomials chosen to minimize the residual after the application of the contraction operator Pi(A)${P}_{i}\left(A\right)$. Two main steps can be identified for each iteration: an OR (Orthogonal Residuals) step where a basis of order $\ell$ is generated by a Bi-CG iteration and an MR (Minimum Residuals) step where the residual is minimized over the basis generated, by a method akin to GMRES. For = 1$\ell =1$, the method corresponds to the Bi-CGSTAB method of Van der Vorst (1989). For > 1$\ell >1$, more information about complex eigenvalues of the iteration matrix can be taken into account, and this may lead to improved convergence and robustness. However, as $\ell$ increases, numerical instabilities may arise. For this reason, a maximum value of = 10$\ell =10$ is imposed, but probably = 4$\ell =4$ is sufficient in most cases.

### Transpose-free Quasi-minimal Residual Method (TFQMR)

The transpose-free quasi-minimal residual method (TFQMR) (see Freund and Nachtigal (1991) and Freund (1993)) is conceptually derived from the CGS method. The residual is minimized over the space of the residual vectors generated by the CGS iterations under the simplifying assumption that residuals are almost orthogonal. In practice, this is not the case but theoretical analysis has proved the validity of the method. This has the effect of remedying the rather irregular convergence behaviour with wild oscillations in the residual norm that can degrade the numerical performance and robustness of the CGS method. In general, the TFQMR method can be expected to converge at least as fast as the CGS method, in terms of number of iterations, although each iteration involves a higher operation count. When the CGS method exhibits irregular convergence, the TFQMR method can produce much smoother, almost monotonic convergence curves. However, the close relationship between the CGS and TFQMR method implies that the overall speed of convergence is similar for both methods. In some cases, the TFQMR method may converge faster than the CGS method.

### General Considerations

For each method, a sequence of solution iterates {xi}$\left\{{x}_{i}\right\}$ is generated such that, hopefully, the sequence of the residual norms {ri}$\left\{‖{r}_{i}‖\right\}$ converges to a required tolerance. Note that, in general, convergence, when it occurs, is not monotonic.
In the RGMRES and Bi-CGSTAB($\ell$) methods above, your program must provide the maximum number of basis vectors used, m$m$ or $\ell$, respectively; however, a smaller number of basis vectors may be generated and used when the stability of the solution process requires this (see Section [Further Comments]).
Faster convergence can be achieved using a preconditioner (see Golub and Van Loan (1996) and Barrett et al. (1994)). A preconditioner maps the original system of equations onto a different system, say
 Ax = b, $A-x-=b-,$ (1)
with, hopefully, better characteristics with respect to its speed of convergence: for example, the condition number of the coefficients matrix can be improved or eigenvalues in its spectrum can be made to coalesce. An orthogonal basis for the Krylov subspace span{Akr0}$\mathrm{span}\left\{{\stackrel{-}{A}}^{\mathit{k}}{\stackrel{-}{r}}_{0}\right\}$, for k = 0,1,$\mathit{k}=0,1,\dots$, is generated and the solution proceeds as outlined above. The algorithms used are such that the solution and residual iterates of the original system are produced, not their preconditioned counterparts. Note that an unsuitable preconditioner or no preconditioning at all may result in a very slow rate, or lack, of convergence. However, preconditioning involves a trade-off between the reduction in the number of iterations required for convergence and the additional computational costs per iteration. Also, setting up a preconditioner may involve non-negligible overheads.
A left preconditioner M1${M}^{-1}$ can be used by the RGMRES, CGS and TFQMR methods, such that A = M1AIn$\stackrel{-}{A}={M}^{-1}A\sim {I}_{n}$ in (1), where In${I}_{n}$ is the identity matrix of order n$n$; a right preconditioner M1${M}^{-1}$ can be used by the Bi-CGSTAB($\ell$) method, such that A = AM1In$\stackrel{-}{A}=A{M}^{-1}\sim {I}_{n}$. These are formal definitions, used only in the design of the algorithms; in practice, only the means to compute the matrix–vector products v = Au$v=Au$ and v = ATu$v={A}^{\mathrm{T}}u$ (the latter only being required when an estimate of A1${‖A‖}_{1}$ or A${‖A‖}_{\infty }$ is computed internally), and to solve the preconditioning equations Mv = u$Mv=u$ are required, i.e., explicit information about M$M$, or its inverse is not required at any stage.
The first termination criterion
 ‖rk‖p ≤ τ (‖b‖p + ‖A‖p × ‖xk‖p) $‖rk‖p ≤ τ ( ‖b‖p + ‖A‖p × ‖xk‖p )$ (2)
is available for all four methods. In (2), p = 1$p=1$, ​ or ​2$\infty \text{​ or ​}2$ and τ$\tau$ denotes a user-specified tolerance subject to max (10,sqrt(n))$\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(10,\sqrt{n}\right)$, ετ < 1$\epsilon \le \tau <1$, where ε$\epsilon$ is the machine precision. Facilities are provided for the estimation of the norm of the coefficients matrix A1${‖A‖}_{1}$ or A${‖A‖}_{\infty }$, when this is not known in advance, by applying Higham's method (see Higham (1988)). Note that A2${‖A‖}_{2}$ cannot be estimated internally. This criterion uses an error bound derived from backward error analysis to ensure that the computed solution is the exact solution of a problem as close to the original as the termination tolerance requires. Termination criteria employing bounds derived from forward error analysis are not used because any such criteria would require information about the condition number κ(A)$\kappa \left(A\right)$ which is not easily obtainable.
The second termination criterion
 ‖rk‖2 ≤ τ ( ‖r0‖2 + σ1 (A) × ‖Δxk‖2 ) $‖r-k‖2 ≤ τ ( ‖ r-0 ‖2 + σ1 (A-) × ‖Δx-k‖2 )$ (3)
is available for all methods except TFQMR. In (3), σ1(A) = A2${\sigma }_{1}\left(\stackrel{-}{A}\right)={‖\stackrel{-}{A}‖}_{2}$ is the largest singular value of the (preconditioned) iteration matrix A$\stackrel{-}{A}$. This termination criterion monitors the progress of the solution of the preconditioned system of equations and is less expensive to apply than criterion (2) for the Bi-CGSTAB($\ell$) method with > 1$\ell >1$. Only the RGMRES method provides facilities to estimate σ1(A)${\sigma }_{1}\left(\stackrel{-}{A}\right)$ internally, when this is not supplied (see Section [Further Comments]).
Termination criterion (2) is the recommended choice, despite its additional costs per iteration when using the Bi-CGSTAB($\ell$) method with > 1$\ell >1$. Also, if the norm of the initial estimate is much larger than the norm of the solution, that is, if x0x$‖{x}_{0}‖\gg ‖x‖$, a dramatic loss of significant digits could result in complete lack of convergence. The use of criterion (2) will enable the detection of such a situation, and the iteration will be restarted at a suitable point. No such restart facilities are provided for criterion (3).
Optionally, a vector w$w$ of user-specified weights can be used in the computation of the vector norms in termination criterion (2), i.e., vp(w) = v(w)p${{‖v‖}_{p}}^{\left(w\right)}={‖{v}^{\left(w\right)}‖}_{p}$, where (v(w))i = wi vi${\left({v}^{\left(w\right)}\right)}_{\mathit{i}}={w}_{\mathit{i}}{v}_{\mathit{i}}$, for i = 1,2,,n$\mathit{i}=1,2,\dots ,n$. Note that the use of weights increases the computational costs.
The sequence of calls to the functions comprising the suite is enforced: first, the setup function nag_sparse_real_gen_basic_setup (f11bd) must be called, followed by the solver nag_sparse_real_gen_basic_solver (f11be). nag_sparse_real_gen_basic_diag (f11bf) can be called either when nag_sparse_real_gen_basic_solver (f11be) is carrying out a monitoring step or after nag_sparse_real_gen_basic_solver (f11be) has completed its tasks. Incorrect sequencing will raise an error condition.
In general, it is not possible to recommend one method in preference to another. RGMRES is often used in the solution of systems arising from PDEs. On the other hand, it can easily stagnate when the size m$m$ of the orthogonal basis is too small, or the preconditioner is not good enough. CGS can be the fastest method, but the computed residuals can exhibit instability which may greatly affect the convergence and quality of the solution. Bi-CGSTAB($\ell$) seems robust and reliable, but it can be slower than the other methods: if a preconditioner is used and > 1$\ell >1$, Bi-CGSTAB($\ell$) computes the solution of the preconditioned system xk = Mxk${\stackrel{-}{x}}_{k}=M{x}_{k}$: the preconditioning equations must be solved to obtain the required solution. The algorithm employed limits to 10%$10%$ or less, when no intermediate monitoring is requested, the number of times the preconditioner has to be thus applied compared with the total number of applications of the preconditioner. TFQMR can be viewed as a more robust variant of the CGS method: it shares the CGS method speed but avoids the CGS fluctuations in the residual, which may give rise to instability. Also, when the termination criterion (2) is used, the CGS, Bi-CGSTAB($\ell$) and TFQMR methods will restart the iteration automatically when necessary in order to solve the given problem.

## References

Arnoldi W (1951) The principle of minimized iterations in the solution of the matrix eigenvalue problem Quart. Appl. Math. 9 17–29
Barrett R, Berry M, Chan T F, Demmel J, Donato J, Dongarra J, Eijkhout V, Pozo R, Romine C and Van der Vorst H (1994) Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods SIAM, Philadelphia
Dias da Cunha R and Hopkins T (1994) PIM 1.1 — the parallel iterative method package for systems of linear equations user's guide — Fortran 77 version Technical Report Computing Laboratory, University of Kent at Canterbury, Kent, UK
Freund R W (1993) A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems SIAM J. Sci. Comput. 14 470–482
Freund R W and Nachtigal N (1991) QMR: a Quasi-Minimal Residual Method for Non-Hermitian Linear Systems Numer. Math. 60 315–339
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Higham N J (1988) FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation ACM Trans. Math. Software 14 381–396
Saad Y and Schultz M (1986) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems SIAM J. Sci. Statist. Comput. 7 856–869
Sleijpen G L G and Fokkema D R (1993) BiCGSTAB()$\left(\ell \right)$ for linear equations involving matrices with complex spectrum ETNA 1 11–32
Sonneveld P (1989) CGS, a fast Lanczos-type solver for nonsymmetric linear systems SIAM J. Sci. Statist. Comput. 10 36–52
Van der Vorst H (1989) Bi-CGSTAB, a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems SIAM J. Sci. Statist. Comput. 13 631–644

## Parameters

### Compulsory Input Parameters

1:     method – string
The iterative method to be used.
method = 'RGMRES'${\mathbf{method}}=\text{'RGMRES'}$
Restarted generalized minimum residual method.
method = 'CGS'${\mathbf{method}}=\text{'CGS'}$
method = 'BICGSTAB'${\mathbf{method}}=\text{'BICGSTAB'}$
Bi-conjugate gradient stabilized ($\ell$) method.
method = 'TFQMR'${\mathbf{method}}=\text{'TFQMR'}$
Transpose-free quasi-minimal residual method.
Constraint: method = 'RGMRES'${\mathbf{method}}=\text{'RGMRES'}$, 'CGS'$\text{'CGS'}$, 'BICGSTAB'$\text{'BICGSTAB'}$ or 'TFQMR'$\text{'TFQMR'}$.
2:     precon – string (length ≥ 1)
Determines whether preconditioning is used.
precon = 'N'${\mathbf{precon}}=\text{'N'}$
No preconditioning.
precon = 'P'${\mathbf{precon}}=\text{'P'}$
Preconditioning.
Constraint: precon = 'N'${\mathbf{precon}}=\text{'N'}$ or 'P'$\text{'P'}$.
3:     n – int64int32nag_int scalar
n$n$, the order of the matrix A$A$.
Constraint: n > 0${\mathbf{n}}>0$.
4:     m – int64int32nag_int scalar
If method = 'RGMRES'${\mathbf{method}}=\text{'RGMRES'}$, m is the dimension m$m$ of the restart subspace.
If method = 'BICGSTAB'${\mathbf{method}}=\text{'BICGSTAB'}$, m is the order $\ell$ of the polynomial Bi-CGSTAB method.
Otherwise, m is not referenced.
Constraints:
• if method = 'RGMRES'${\mathbf{method}}=\text{'RGMRES'}$, 0 < mmin (n,50)$0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},50\right)$;
• if method = 'BICGSTAB'${\mathbf{method}}=\text{'BICGSTAB'}$, 0 < mmin (n,10)$0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},10\right)$.
5:     tol – double scalar
The tolerance τ$\tau$ for the termination criterion. If tol0.0,τ = max (sqrt(ε),sqrt(n)ε)${\mathbf{tol}}\le 0.0,\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(\sqrt{\epsilon },\sqrt{n}\epsilon \right)$ is used, where ε$\epsilon$ is the machine precision. Otherwise τ = max (tol,10ε,sqrt(n)ε)$\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{tol}},10\epsilon ,\sqrt{n}\epsilon \right)$ is used.
Constraint: tol < 1.0${\mathbf{tol}}<1.0$.
6:     maxitn – int64int32nag_int scalar
The maximum number of iterations.
Constraint: maxitn > 0${\mathbf{maxitn}}>0$.
7:     anorm – double scalar
If anorm > 0.0${\mathbf{anorm}}>0.0$, the value of Ap${‖A‖}_{p}$ to be used in the termination criterion (2) (iterm = 1${\mathbf{iterm}}=1$).
If anorm0.0${\mathbf{anorm}}\le 0.0$, iterm = 1${\mathbf{iterm}}=1$ and norm = '1'${\mathbf{norm}}=\text{'1'}$ or 'I'$\text{'I'}$, then A1 = A${‖A‖}_{1}={‖A‖}_{\infty }$ is estimated internally by nag_sparse_real_gen_basic_solver (f11be).
If iterm = 2${\mathbf{iterm}}=2$, anorm is not referenced.
Constraint: if iterm = 1${\mathbf{iterm}}=1$ and norm = '2'${\mathbf{norm}}=\text{'2'}$, anorm > 0.0${\mathbf{anorm}}>0.0$.
8:     sigmax – double scalar
If iterm = 2${\mathbf{iterm}}=2$, the largest singular value σ1${\sigma }_{1}$ of the preconditioned iteration matrix; otherwise, sigmax is not referenced.
If sigmax0.0${\mathbf{sigmax}}\le 0.0$, iterm = 2${\mathbf{iterm}}=2$ and method = 'RGMRES'${\mathbf{method}}=\text{'RGMRES'}$, then the value of σ1${\sigma }_{1}$ will be estimated internally.
Constraint: if method = 'CGS'${\mathbf{method}}=\text{'CGS'}$ or 'BICGSTAB'$\text{'BICGSTAB'}$ and iterm = 2${\mathbf{iterm}}=2$, sigmax > 0.0${\mathbf{sigmax}}>0.0$.
9:     monit – int64int32nag_int scalar
If monit > 0${\mathbf{monit}}>0$, the frequency at which a monitoring step is executed by nag_sparse_real_gen_basic_solver (f11be): if method = 'CGS'${\mathbf{method}}=\text{'CGS'}$ or 'TFQMR'$\text{'TFQMR'}$, a monitoring step is executed every monit iterations; otherwise, a monitoring step is executed every monit super-iterations (groups of up to m$m$ or $\ell$ iterations for RGMRES or Bi-CGSTAB($\ell$), respectively).
There are some additional computational costs involved in monitoring the solution and residual vectors when the Bi-CGSTAB($\ell$) method is used with > 1$\ell >1$.
Constraint: ${\mathbf{monit}}\le {\mathbf{maxitn}}$.
10:   lwork – int64int32nag_int scalar
The dimension of the array work as declared in the (sub)program from which nag_sparse_real_gen_basic_setup (f11bd) is called.
Constraint: lwork100${\mathbf{lwork}}\ge 100$.
Note:  although the minimum value of lwork ensures the correct functioning of nag_sparse_real_gen_basic_setup (f11bd), a larger value is required by the other functions in the suite, namely nag_sparse_real_gen_basic_solver (f11be) and nag_sparse_real_gen_basic_diag (f11bf). The required value is as follows:
 Method Requirements RGMRES lwork = 100 + n(m + 3) + m(m + 5) + 1${\mathbf{lwork}}=100+n\left(m+3\right)+m\left(m+5\right)+1$, where m$m$ is the dimension of the basis. CGS lwork = 100 + 7n${\mathbf{lwork}}=100+7n$. Bi-CGSTAB(ℓ$\ell$) lwork = 100 + (2n + ℓ)(ℓ + 2) + p${\mathbf{lwork}}=100+\left(2n+\ell \right)\left(\ell +2\right)+p$, where ℓ$\ell$ is the order of the method. TFQMR lwork = 100 + 10n${\mathbf{lwork}}=100+10n$,
where
 p = 2n$p=2n$ if ℓ > 1$\ell >1$ and iterm = 2${\mathbf{iterm}}=2$ was supplied. p = n$p=n$ if ℓ > 1$\ell >1$ and a preconditioner is used or iterm = 2${\mathbf{iterm}}=2$ was supplied. p = 0$p=0$ otherwise.

### Optional Input Parameters

1:     norm_p – string (length ≥ 1)
Defines the matrix and vector norm to be used in the termination criteria.
norm = '1'${\mathbf{norm}}=\text{'1'}$
l1${l}_{1}$ norm.
norm = 'I'${\mathbf{norm}}=\text{'I'}$
l${l}_{\infty }$ norm.
norm = '2'${\mathbf{norm}}=\text{'2'}$
l2${l}_{2}$ norm.
Default:
• if iterm = 1${\mathbf{iterm}}=1$, 'I' $\text{'I'}$;
• otherwise '2' $\text{'2'}$.
Constraints:
• if iterm = 1${\mathbf{iterm}}=1$, norm = '1'${\mathbf{norm}}=\text{'1'}$, 'I'$\text{'I'}$ or '2'$\text{'2'}$;
• if iterm = 2${\mathbf{iterm}}=2$, norm = '2'${\mathbf{norm}}=\text{'2'}$.
2:     weight – string (length ≥ 1)
Specifies whether a vector w$w$ of user-supplied weights is to be used in the computation of the vector norms required in termination criterion (2) (iterm = 1${\mathbf{iterm}}=1$): vp(w) = v(w)p${{‖v‖}_{p}}^{\left(w\right)}={‖{v}^{\left(w\right)}‖}_{p}$, where vi(w) = wi vi${v}_{\mathit{i}}^{\left(w\right)}={w}_{\mathit{i}}{v}_{\mathit{i}}$, for i = 1,2,,n$\mathit{i}=1,2,\dots ,n$. The suffix p = 1,2,$p=1,2,\infty$ denotes the vector norm used, as specified by the parameter norm_p. Note that weights cannot be used when iterm = 2${\mathbf{iterm}}=2$, i.e., when criterion (3) is used.
weight = 'W'${\mathbf{weight}}=\text{'W'}$
User-supplied weights are to be used and must be supplied on initial entry to nag_sparse_real_gen_basic_solver (f11be).
weight = 'N'${\mathbf{weight}}=\text{'N'}$
All weights are implicitly set equal to one. Weights do not need to be supplied on initial entry to nag_sparse_real_gen_basic_solver (f11be).
Default: 'N'$\text{'N'}$
Constraints:
• if iterm = 1${\mathbf{iterm}}=1$, weight = 'W'${\mathbf{weight}}=\text{'W'}$ or 'N'$\text{'N'}$;
• if iterm = 2${\mathbf{iterm}}=2$, weight = 'N'${\mathbf{weight}}=\text{'N'}$.
3:     iterm – int64int32nag_int scalar
Defines the termination criterion to be used.
iterm = 1${\mathbf{iterm}}=1$
Use the termination criterion defined in (2).
iterm = 2${\mathbf{iterm}}=2$
Use the termination criterion defined in (3).
Default: 1$1$
Constraints:
• if method = 'TFQMR'${\mathbf{method}}=\text{'TFQMR'}$ or weight = 'W'${\mathbf{weight}}=\text{'W'}$ or norm = '2'${\mathbf{norm}}=\text{'2'}$, iterm = 1${\mathbf{iterm}}=1$;
• otherwise iterm = 1${\mathbf{iterm}}=1$ or 2$2$.
Note: iterm = 2${\mathbf{iterm}}=2$ is only appropriate for a restricted set of choices for method, norm_p and weight; that is norm = '2'${\mathbf{norm}}=\text{'2'}$, weight = 'N'${\mathbf{weight}}=\text{'N'}$ and method'TFQMR'${\mathbf{method}}\ne \text{'TFQMR'}$.

None.

### Output Parameters

1:     lwreq – int64int32nag_int scalar
The minimum amount of workspace required by nag_sparse_real_gen_basic_solver (f11be). (See also Section [Parameters] in (f11be).)
2:     work(lwork) – double array
The array work is initialized by nag_sparse_real_gen_basic_setup (f11bd). It must not be modified before calling the next function in the suite, namely nag_sparse_real_gen_basic_solver (f11be).
3:     ifail – int64int32nag_int scalar
${\mathrm{ifail}}={\mathbf{0}}$ unless the function detects an error (see [Error Indicators and Warnings]).

## Error Indicators and Warnings

Errors or warnings detected by the function:
ifail = i${\mathbf{ifail}}=-i$
If ifail = i${\mathbf{ifail}}=-i$, parameter i$i$ had an illegal value on entry. The parameters are numbered as follows:
1: method, 2: precon, 3: norm_p, 4: weight, 5: iterm, 6: n, 7: m, 8: tol, 9: maxitn, 10: anorm, 11: sigmax, 12: monit, 13: lwreq, 14: work, 15: lwork, 16: ifail.
ifail = 1${\mathbf{ifail}}=1$
nag_sparse_real_gen_basic_setup (f11bd) has been called out of sequence.

## Accuracy

Not applicable.

RGMRES can estimate internally the maximum singular value σ1${\sigma }_{1}$ of the iteration matrix, using σ1T1${\sigma }_{1}\sim {‖T‖}_{1}$, where T$T$ is the upper triangular matrix obtained by QR$QR$ factorization of the upper Hessenberg matrix generated by the Arnoldi process. The computational costs of this computation are negligible when compared to the overall costs.
Loss of orthogonality in the RGMRES method, or of bi-orthogonality in the Bi-CGSTAB($\ell$) method may degrade the solution and speed of convergence. For both methods, the algorithms employed include checks on the basis vectors so that the number of basis vectors used for a given super-iteration may be less than the value specified in the input parameter m. Also, if termination criterion (2) is used the CGS, Bi-CGSTAB($\ell$) and TFQMR methods will restart automatically the computation from the last available iterates, when the stability of the solution process requires it.
Termination criterion (3), when available, involves only the residual (or norm of the residual) produced directly by the iteration process: this may differ from the norm of the true residual k = bAxk${\stackrel{~}{r}}_{k}=b-A{x}_{k}$, particularly when the norm of the residual is very small. Also, if the norm of the initial estimate of the solution is much larger than the norm of the exact solution, convergence can be achieved despite very large errors in the solution. On the other hand, termination criterion (3) is cheaper to use and inspects the progress of the actual iteration. Termination criterion (2) should be preferred in most cases, despite its slightly larger costs.

## Example

```function nag_sparse_real_gen_basic_setup_example
method = 'BICGSTAB';
precon = 'P';
n = 8;
m = int64(1);
nz = 24;
a = zeros(10000, 1);
a(1:24) = [2;-1;1;4;-3;2;-7;2;3;-4;5;5;-1;8;-3;-6;5;2;-5;-1;6;-1;2;3];
irow = zeros(10000, 1, 'int64');
irow(1:24) = [int64(1);1;1;2;2;2;3;3;4;4;4;4;5;5;5;6;6;6;7;7;7;8;8;8];
icol = zeros(10000, 1, 'int64');
icol(1:24) = [int64(1);4;8;1;2;5;3;6;1;3;4;7;2;5;7;1;3;6;3;5;7;2;6;8];
lfill = int64(0);
ipivp = zeros(8, 1, 'int64');
ipivq = zeros(8, 1, 'int64');
dtol = 0;
milu = 'N';
tol = 1e-08;
maxitn = int64(20);
anorm = 0;
sigmax = 0;
monit = int64(1);
lwork = int64(6000);
irevcm = int64(0);
u = zeros(8, 1);
v = [6; 8; -9; 46; 17; 21; 22; 34];
wgt = zeros(8, 1);
[a, irow, icol, ipivp, ipivq, istr, idiag, nnzc, npivm, ifail] = ...
nag_sparse_real_gen_precon_ilu(int64(nz), a, irow, icol, lfill,  ...
dtol, milu, ipivp, ipivq);
[lwreq, work, ifail] = ...
nag_sparse_real_gen_basic_setup(method, precon, int64(n), m, tol,  ...
maxitn, anorm, sigmax, monit, lwork, 'norm_p', '1');
while (irevcm ~= 4)
[irevcm, u, v, work, ifail] = ...
nag_sparse_real_gen_basic_solver(irevcm, u, v, wgt, work);

if (irevcm == -1)
[v, ifail] = ...
nag_sparse_real_gen_matvec('T', a(1:nz), irow(1:nz), icol(1:nz), 'N', u);
elseif (irevcm == 1)
[v, ifail] = ...
nag_sparse_real_gen_matvec('N', a(1:nz), irow(1:nz), icol(1:nz), 'N', u);
elseif (irevcm == 2)
[v, ifail] = ...
nag_sparse_real_gen_precon_ilu_solve('N', a, irow, icol, ipivp, ipivq,  ...
istr, idiag, 'N', u);
if (ifail ~= 0)
irevcm = 6;
end
elseif (irevcm == 3)
[itn, stplhs, stprhs, anorm, sigmax, ifail] = ...
nag_sparse_real_gen_basic_diag(work);
fprintf('\nMonitoring at iteration number %d\nresidual norm: %14.4e\n',  ...
itn, stplhs);
fprintf('\n   Solution Vector  Residual Vector\n');
for i = 1:n
fprintf('%+16.4e %+16.4e\n', u(i), v(i));
end
end
end
% Get information about the computation
[itn, stplhs, stprhs, anorm, sigmax, ifail] =  ...
nag_sparse_real_gen_basic_diag(work);
fprintf('\nNumber of iterations for convergence: %d\n', itn);
fprintf('Residual norm:                           %14.4e\n', stplhs);
fprintf('Right-hand side of termination criteria: %14.4e\n', stprhs);
fprintf('i-norm of matrix a:                      %14.4e\n', anorm);
fprintf('\n   Solution Vector  Residual Vector\n');
for i = 1:n
fprintf('%+16.4e %+16.4e\n', u(i), v(i));
end
```
```

Monitoring at iteration number 1
residual norm:     1.4059e+02

Solution Vector  Residual Vector
-4.5858e+00      +1.5256e+01
+1.0154e+00      +2.6624e+01
-2.2234e+00      -8.7498e+00
+6.0097e+00      +1.8602e+01
+1.3827e+00      +8.2821e+00
-7.9070e+00      +2.0416e+01
+4.4270e-01      +9.6094e+00
+5.9248e+00      +3.3055e+01

Monitoring at iteration number 2
residual norm:     3.2742e+01

Solution Vector  Residual Vector
+4.1642e+00      -2.9585e+00
+4.9370e+00      -5.5523e+00
+4.8101e+00      +8.2070e-01
+5.4324e+00      -1.6828e+01
+5.8531e+00      +5.5975e-01
+1.1925e+01      -1.9150e+00
+8.4826e+00      +1.0081e+00
+6.0625e+00      -3.1004e+00

Number of iterations for convergence: 3
Residual norm:                               5.3402e-09
Right-hand side of termination criteria:     5.5900e-06
i-norm of matrix a:                          1.1000e+01

Solution Vector  Residual Vector
+1.0000e+00      -6.9779e-10
+2.0000e+00      -1.3442e-09
+3.0000e+00      +1.1569e-10
+4.0000e+00      -1.6579e-09
+5.0000e+00      +3.2458e-10
+6.0000e+00      -2.6994e-10
+7.0000e+00      +4.9305e-10
+8.0000e+00      -4.3705e-10

```
```function f11bd_example
method = 'BICGSTAB';
precon = 'P';
n = 8;
m = int64(1);
nz = 24;
a = zeros(10000, 1);
a(1:24) = [2; -1; 1; 4; -3; 2; -7; 2; 3; -4; 5; 5; -1; 8; -3; -6; 5; 2; -5; -1; 6; -1; 2; 3];
irow = zeros(10000, 1, 'int64');
irow(1:24) = [int64(1);1;1;2;2;2;3;3;4;4;4;4;5;5;5;6;6;6;7;7;7;8;8;8];
icol = zeros(10000, 1, 'int64');
icol(1:24) = [int64(1);4;8;1;2;5;3;6;1;3;4;7;2;5;7;1;3;6;3;5;7;2;6;8];
lfill = int64(0);
ipivp = zeros(8, 1, 'int64');
ipivq = zeros(8, 1, 'int64');
dtol = 0;
milu = 'N';
tol = 1e-08;
maxitn = int64(20);
anorm = 0;
sigmax = 0;
monit = int64(1);
lwork = int64(6000);
irevcm = int64(0);
u = zeros(8, 1);
v = [6; 8; -9; 46; 17; 21; 22; 34];
wgt = zeros(8, 1);
[a, irow, icol, ipivp, ipivq, istr, idiag, nnzc, npivm, ifail] = ...
f11da(int64(nz), a, irow, icol, lfill, dtol, milu, ipivp, ipivq);
[lwreq, work, ifail] = ...
f11bd(method, precon, int64(n), m, tol, maxitn, anorm, sigmax, monit, lwork, 'norm_p', '1');
while (irevcm ~= 4)
[irevcm, u, v, work, ifail] = f11be(irevcm, u, v, wgt, work);

if (irevcm == -1)
[v, ifail] = f11xa('T', a(1:nz), irow(1:nz), icol(1:nz), 'N', u);
elseif (irevcm == 1)
[v, ifail] = f11xa('N', a(1:nz), irow(1:nz), icol(1:nz), 'N', u);
elseif (irevcm == 2)
[v, ifail] = f11db('N', a, irow, icol, ipivp, ipivq, istr, idiag, 'N', u);
if (ifail ~= 0)
irevcm = 6;
end
elseif (irevcm == 3)
[itn, stplhs, stprhs, anorm, sigmax, ifail] = f11bf(work);
fprintf('\nMonitoring at iteration number %d\nresidual norm: %14.4e\n', itn, stplhs);
fprintf('\n   Solution Vector  Residual Vector\n');
for i = 1:n
fprintf('%+16.4e %+16.4e\n', u(i), v(i));
end
end
end
% Get information about the computation
[itn, stplhs, stprhs, anorm, sigmax, ifail] = f11bf(work);
fprintf('\nNumber of iterations for convergence: %d\n', itn);
fprintf('Residual norm:                           %14.4e\n', stplhs);
fprintf('Right-hand side of termination criteria: %14.4e\n', stprhs);
fprintf('i-norm of matrix a:                      %14.4e\n', anorm);
fprintf('\n   Solution Vector  Residual Vector\n');
for i = 1:n
fprintf('%+16.4e %+16.4e\n', u(i), v(i));
end
```
```

Monitoring at iteration number 1
residual norm:     1.4059e+02

Solution Vector  Residual Vector
-4.5858e+00      +1.5256e+01
+1.0154e+00      +2.6624e+01
-2.2234e+00      -8.7498e+00
+6.0097e+00      +1.8602e+01
+1.3827e+00      +8.2821e+00
-7.9070e+00      +2.0416e+01
+4.4270e-01      +9.6094e+00
+5.9248e+00      +3.3055e+01

Monitoring at iteration number 2
residual norm:     3.2742e+01

Solution Vector  Residual Vector
+4.1642e+00      -2.9585e+00
+4.9370e+00      -5.5523e+00
+4.8101e+00      +8.2070e-01
+5.4324e+00      -1.6828e+01
+5.8531e+00      +5.5975e-01
+1.1925e+01      -1.9150e+00
+8.4826e+00      +1.0081e+00
+6.0625e+00      -3.1004e+00

Number of iterations for convergence: 3
Residual norm:                               5.3405e-09
Right-hand side of termination criteria:     5.5900e-06
i-norm of matrix a:                          1.1000e+01

Solution Vector  Residual Vector
+1.0000e+00      -6.9784e-10
+2.0000e+00      -1.3443e-09
+3.0000e+00      +1.1570e-10
+4.0000e+00      -1.6580e-09
+5.0000e+00      +3.2460e-10
+6.0000e+00      -2.6996e-10
+7.0000e+00      +4.9307e-10
+8.0000e+00      -4.3708e-10

```