f11 Chapter Contents
f11 Chapter Introduction
NAG C Library Manual

NAG Library Function Documentnag_sparse_nherm_sol (f11dsc)

1  Purpose

nag_sparse_nherm_sol (f11dsc) 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, without preconditioning, with Jacobi, or with SSOR preconditioning.

2  Specification

 #include #include
 void nag_sparse_nherm_sol (Nag_SparseNsym_Method method, Nag_SparseNsym_PrecType precon, Integer n, Integer nnz, const Complex a[], const Integer irow[], const Integer icol[], double omega, const Complex b[], Integer m, double tol, Integer maxitn, Complex x[], double *rnorm, Integer *itn, NagError *fail)

3  Description

nag_sparse_nherm_sol (f11dsc) solves a complex sparse non-Hermitian system of linear equations:
 $Ax=b,$
using an 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_sol (f11dsc) allows the following choices for the preconditioner:
• – no preconditioning;
• – Jacobi preconditioning (see Young (1971));
• – symmetric successive-over-relaxation (SSOR) preconditioning (see Young (1971)).
For incomplete $LU$ (ILU) preconditioning see nag_sparse_nherm_fac_sol (f11dqc).
The matrix $A$ is represented in coordinate storage (CS) format (see Section 2.1.1 in the f11 Chapter Introduction) in the arrays a, irow and icol. The array a holds the nonzero entries in the matrix, while irow and icol hold the corresponding row and column indices.
nag_sparse_nherm_sol (f11dsc) is a Black Box function which calls nag_sparse_nherm_basic_setup (f11brc), nag_sparse_nherm_basic_solver (f11bsc) and nag_sparse_nherm_basic_diagnostic (f11btc). If you wish to use an alternative storage scheme, preconditioner, or termination criterion, or require additional diagnostic information, you should call these underlying functions directly.

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
Young D (1971) Iterative Solution of Large Linear Systems Academic Press, New York

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}$
Conjugate gradient squared method.
${\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:     preconNag_SparseNsym_PrecTypeInput
On entry: specifies the type of preconditioning to be used.
${\mathbf{precon}}=\mathrm{Nag_SparseNsym_NoPrec}$
No preconditioning.
${\mathbf{precon}}=\mathrm{Nag_SparseNsym_JacPrec}$
Jacobi.
${\mathbf{precon}}=\mathrm{Nag_SparseNsym_SSORPrec}$
Symmetric successive-over-relaxation (SSOR).
Constraint: ${\mathbf{precon}}=\mathrm{Nag_SparseNsym_NoPrec}$, $\mathrm{Nag_SparseNsym_JacPrec}$ or $\mathrm{Nag_SparseNsym_SSORPrec}$.
3:     nIntegerInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 1$.
4:     nnzIntegerInput
On entry: the number of nonzero elements in the matrix $A$.
Constraint: $1\le {\mathbf{nnz}}\le {{\mathbf{n}}}^{2}$.
5:     a[nnz]const ComplexInput
On entry: the nonzero elements of the matrix $A$, ordered by increasing row index, and by increasing column index within each row. Multiple entries for the same row and column indices are not permitted. The function nag_sparse_nherm_sort (f11znc) may be used to order the elements in this way.
6:     irow[nnz]const IntegerInput
7:     icol[nnz]const IntegerInput
On entry: the row and column indices of the nonzero elements supplied in a.
Constraints:
irow and icol must satisfy the following constraints (which may be imposed by a call to nag_sparse_nherm_sort (f11znc)):
• $1\le {\mathbf{irow}}\left[\mathit{i}\right]\le {\mathbf{n}}$ and $1\le {\mathbf{icol}}\left[\mathit{i}\right]\le {\mathbf{n}}$, for $\mathit{i}=0,1,\dots ,{\mathbf{nnz}}-1$;
• either ${\mathbf{irow}}\left[\mathit{i}-1\right]<{\mathbf{irow}}\left[\mathit{i}\right]$ or both ${\mathbf{irow}}\left[\mathit{i}-1\right]={\mathbf{irow}}\left[\mathit{i}\right]$ and ${\mathbf{icol}}\left[\mathit{i}-1\right]<{\mathbf{icol}}\left[\mathit{i}\right]$, for $\mathit{i}=1,2,\dots ,{\mathbf{nnz}}-1$.
On entry: if ${\mathbf{precon}}=\mathrm{Nag_SparseNsym_SSORPrec}$, omega is the relaxation argument $\omega$ to be used in the SSOR method. Otherwise omega need not be initialized and is not referenced.
Constraint: $0.0<{\mathbf{omega}}<2.0$.
9:     b[n]const ComplexInput
On entry: the right-hand side vector $b$.
10:   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)$.
11:   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$.
12:   maxitnIntegerInput
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxitn}}\ge 1$.
13:   x[n]ComplexInput/Output
On entry: an initial approximation to the solution vector $x$.
On exit: an improved approximation to the solution vector $x$.
14:   rnormdouble *Output
On exit: the final value of the residual norm ${‖{r}_{k}‖}_{\infty }$, where $k$ is the output value of itn.
15:   itnInteger *Output
On exit: the number of iterations carried out.
16:   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_ENUM_INT_2
On entry, ${\mathbf{method}}=〈\mathit{\text{value}}〉$, ${\mathbf{n}}=〈\mathit{\text{value}}〉$ and ${\mathbf{m}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{method}}=\mathrm{Nag_SparseNsym_BiCGSTAB}$, $0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},10\right)$.
On entry, ${\mathbf{method}}=〈\mathit{\text{value}}〉$, ${\mathbf{n}}=〈\mathit{\text{value}}〉$ and ${\mathbf{m}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{method}}=\mathrm{Nag_SparseNsym_RGMRES}$, $0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},50\right)$.
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{nnz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: $1\le {\mathbf{nnz}}\le {{\mathbf{n}}}^{2}$.
NE_INT_3
On entry, ${\mathbf{m}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: $0<{\mathbf{m}}\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},〈\mathit{\text{value}}〉\right)$.
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}}$.
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}}$.
NE_NOT_STRICTLY_INCREASING
On entry, ${\mathbf{a}}\left[i-1\right]$ is out of order: $i=〈\mathit{\text{value}}〉$.
On entry, the location (${\mathbf{irow}}\left[i-1\right],{\mathbf{icol}}\left[i-1\right]$) is a duplicate: $i=〈\mathit{\text{value}}〉$.
NE_REAL
On entry, ${\mathbf{omega}}=〈\mathit{\text{value}}〉$.
Constraint: $0.0<{\mathbf{omega}}<2.0$
On entry, ${\mathbf{tol}}=〈\mathit{\text{value}}〉$.
Constraint:${\mathbf{tol}}<1.0$.
NE_ZERO_DIAG_ELEM
The matrix $A$ has a zero diagonal entry in row $〈\mathit{\text{value}}〉$.
The matrix $A$ has no diagonal entry in row $〈\mathit{\text{value}}〉$.

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_sol (f11dsc) for each iteration is roughly proportional to nnz.
The number of iterations required to achieve a prescribed accuracy cannot easily be determined a priori, as it can depend dramatically on the conditioning and spectrum of the preconditioned coefficient matrix $\stackrel{-}{A}={M}^{-1}A$, for some preconditioning matrix $M$.

9  Example

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

9.1  Program Text

Program Text (f11dsce.c)

9.2  Program Data

Program Data (f11dsce.d)

9.3  Program Results

Program Results (f11dsce.r)