f11 Chapter Contents
f11 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_sparse_nherm_fac_sol (f11dqc)

## 1  Purpose

nag_sparse_nherm_fac_sol (f11dqc) solves a complex sparse non-Hermitian system of linear equations, represented in coordinate storage format, using a restarted generalized minimal residual (RGMRES), conjugate gradient squared (CGS), stabilized bi-conjugate gradient (Bi-CGSTAB), or transpose-free quasi-minimal residual (TFQMR) method, with incomplete $LU$ preconditioning.

## 2  Specification

 #include #include
 void nag_sparse_nherm_fac_sol (Nag_SparseNsym_Method method, Integer n, Integer nnz, const Complex a[], Integer la, const Integer irow[], const Integer icol[], const Integer ipivp[], const Integer ipivq[], const Integer istr[], const Integer idiag[], const Complex b[], Integer m, double tol, Integer maxitn, Complex x[], double *rnorm, Integer *itn, NagError *fail)

## 3  Description

nag_sparse_nherm_fac_sol (f11dqc) solves a complex sparse non-Hermitian linear system of equations
 $Ax=b,$
using a preconditioned RGMRES (see Saad and Schultz (1986)), CGS (see Sonneveld (1989)), Bi-CGSTAB($\ell$) (see Van der Vorst (1989) and Sleijpen and Fokkema (1993)), or TFQMR (see Freund and Nachtigal (1991) and Freund (1993)) method.
nag_sparse_nherm_fac_sol (f11dqc) uses the incomplete $LU$ factorization determined by nag_sparse_nherm_fac (f11dnc) as the preconditioning matrix. A call to nag_sparse_nherm_fac_sol (f11dqc) must always be preceded by a call to nag_sparse_nherm_fac (f11dnc). Alternative preconditioners for the same storage scheme are available by calling nag_sparse_nherm_sol (f11dsc).
The matrix $A$, and the preconditioning matrix $M$, are represented in coordinate storage (CS) format (see Section 2.1.1 in the f11 Chapter Introduction) in the arrays a, irow and icol, as returned from nag_sparse_nherm_fac (f11dnc). The array a holds the nonzero entries in these matrices, while irow and icol hold the corresponding row and column indices.

## 4  References

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
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

## 5  Arguments

1:     methodNag_SparseNsym_MethodInput
On entry: specifies the iterative method to be used.
${\mathbf{method}}=\mathrm{Nag_SparseNsym_RGMRES}$
Restarted generalized minimum residual method.
${\mathbf{method}}=\mathrm{Nag_SparseNsym_CGS}$
${\mathbf{method}}=\mathrm{Nag_SparseNsym_BiCGSTAB}$
Bi-conjugate gradient stabilized ($\ell$) method.
${\mathbf{method}}=\mathrm{Nag_SparseNsym_TFQMR}$
Transpose-free quasi-minimal residual method.
Constraint: ${\mathbf{method}}=\mathrm{Nag_SparseNsym_RGMRES}$, $\mathrm{Nag_SparseNsym_CGS}$, $\mathrm{Nag_SparseNsym_BiCGSTAB}$ or $\mathrm{Nag_SparseNsym_TFQMR}$.
2:     nIntegerInput
On entry: $n$, the order of the matrix $A$. This must be the same value as was supplied in the preceding call to nag_sparse_nherm_fac (f11dnc).
Constraint: ${\mathbf{n}}\ge 1$.
3:     nnzIntegerInput
On entry: the number of nonzero elements in the matrix $A$. This must be the same value as was supplied in the preceding call to nag_sparse_nherm_fac (f11dnc).
Constraint: $1\le {\mathbf{nnz}}\le {{\mathbf{n}}}^{2}$.
4:     a[la]const ComplexInput
On entry: the values returned in the array a by a previous call to nag_sparse_nherm_fac (f11dnc).
5:     laIntegerInput
On entry: the dimension of the arrays a, irow and icol. This must be the same value as was supplied in the preceding call to nag_sparse_nherm_fac (f11dnc).
Constraint: ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
6:     irow[la]const IntegerInput
7:     icol[la]const IntegerInput
8:     ipivp[n]const IntegerInput
9:     ipivq[n]const IntegerInput
10:   istr[${\mathbf{n}}+1$]const IntegerInput
11:   idiag[n]const IntegerInput
On entry: the values returned in arrays irow, icol, ipivp, ipivq, istr and idiag by a previous call to nag_sparse_nherm_fac (f11dnc).
ipivp and ipivq are restored on exit.
12:   b[n]const ComplexInput
On entry: the right-hand side vector $b$.
13:   mIntegerInput
On entry: if ${\mathbf{method}}=\mathrm{Nag_SparseNsym_RGMRES}$, m is the dimension of the restart subspace.
If ${\mathbf{method}}=\mathrm{Nag_SparseNsym_BiCGSTAB}$, m is the order $\ell$ of the polynomial Bi-CGSTAB method.
Otherwise, m is not referenced.
Constraints:
• if ${\mathbf{method}}=\mathrm{Nag_SparseNsym_RGMRES}$, $0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},50\right)$;
• if ${\mathbf{method}}=\mathrm{Nag_SparseNsym_BiCGSTAB}$, $0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},10\right)$.
14:   toldoubleInput
On entry: the required tolerance. Let ${x}_{k}$ denote the approximate solution at iteration $k$, and ${r}_{k}$ the corresponding residual. The algorithm is considered to have converged at iteration $k$ if
 $rk∞≤τ×b∞+A∞xk∞.$
If ${\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 $\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{tol}},10\epsilon ,\sqrt{n}\epsilon \right)$ is used.
Constraint: ${\mathbf{tol}}<1.0$.
15:   maxitnIntegerInput
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxitn}}\ge 1$.
16:   x[n]ComplexInput/Output
On entry: an initial approximation to the solution vector $x$.
On exit: an improved approximation to the solution vector $x$.
17:   rnormdouble *Output
On exit: the final value of the residual norm ${‖{r}_{k}‖}_{\infty }$, where $k$ is the output value of itn.
18:   itnInteger *Output
On exit: the number of iterations carried out.
19:   failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_ACCURACY
The required accuracy could not be obtained. However a reasonable accuracy may have been achieved.
NE_ALG_FAIL
Algorithmic breakdown. A solution is returned, although it is possible that it is completely inaccurate.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_CONVERGENCE
The solution has not converged after $〈\mathit{\text{value}}〉$ iterations.
NE_INT
On entry, ${\mathbf{maxitn}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{maxitn}}\ge 1$.
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 1$.
On entry, ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{nnz}}\ge 1$.
NE_INT_2
On entry, ${\mathbf{la}}=〈\mathit{\text{value}}〉$ and ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
On entry, ${\mathbf{m}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{m}}\ge 1$ and ${\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},〈\mathit{\text{value}}〉\right)$.
On entry, ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{nnz}}\le {{\mathbf{n}}}^{2}$.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_INVALID_CS
On entry, $i=〈\mathit{\text{value}}〉$, ${\mathbf{icol}}\left[i-1\right]=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{icol}}\left[i-1\right]\ge 1$ and ${\mathbf{icol}}\left[i-1\right]\le {\mathbf{n}}$.
Check that a, irow, icol, ipivp, ipivq, istr and idiag have not been corrupted between calls to nag_sparse_nherm_fac_sol (f11dqc) and nag_sparse_nherm_fac (f11dnc).
On entry, $i=〈\mathit{\text{value}}〉$, ${\mathbf{irow}}\left[i-1\right]=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{irow}}\left[i-1\right]\ge 1$ and ${\mathbf{irow}}\left[i-1\right]\le {\mathbf{n}}$.
Check that a, irow, icol, ipivp, ipivq, istr and idiag have not been corrupted between calls to nag_sparse_nherm_fac_sol (f11dqc) and nag_sparse_nherm_fac (f11dnc).
NE_INVALID_CS_PRECOND
The CS representation of the preconditioner is invalid.
Check that a, irow, icol, ipivp, ipivq, istr and idiag have not been corrupted between calls to nag_sparse_nherm_fac_sol (f11dqc) and nag_sparse_nherm_fac (f11dnc).
NE_NOT_STRICTLY_INCREASING
On entry, ${\mathbf{a}}\left[i-1\right]$ is out of order: $i=〈\mathit{\text{value}}〉$.
Check that a, irow, icol, ipivp, ipivq, istr and idiag have not been corrupted between calls to nag_sparse_nherm_fac_sol (f11dqc) and nag_sparse_nherm_fac (f11dnc).
On entry, the location (${\mathbf{irow}}\left[i-1\right],{\mathbf{icol}}\left[i-1\right]$) is a duplicate: $i=〈\mathit{\text{value}}〉$.
Check that a, irow, icol, ipivp, ipivq, istr and idiag have not been corrupted between calls to nag_sparse_nherm_fac_sol (f11dqc) and nag_sparse_nherm_fac (f11dnc).
NE_REAL
On entry, ${\mathbf{tol}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{tol}}<1.0$.

## 7  Accuracy

On successful termination, the final residual ${r}_{k}=b-A{x}_{k}$, where $k={\mathbf{itn}}$, satisfies the termination criterion
 $rk∞≤τ×b∞+A∞xk∞.$
The value of the final residual norm is returned in rnorm.

The time taken by nag_sparse_nherm_fac_sol (f11dqc) for each iteration is roughly proportional to the value of nnzc returned from the preceding call to nag_sparse_nherm_fac (f11dnc).
The number of iterations required to achieve a prescribed accuracy cannot be easily determined a priori, as it can depend dramatically on the conditioning and spectrum of the preconditioned coefficient matrix $\stackrel{-}{A}={M}^{-1}A$.

## 9  Example

This example solves a complex sparse non-Hermitian linear system of equations using the CGS method, with incomplete $LU$ preconditioning.

### 9.1  Program Text

Program Text (f11dqce.c)

### 9.2  Program Data

Program Data (f11dqce.d)

### 9.3  Program Results

Program Results (f11dqce.r)