f11 Chapter Contents
f11 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_sparse_herm_sol (f11jsc)

## 1  Purpose

nag_sparse_herm_sol (f11jsc) solves a complex sparse Hermitian system of linear equations, represented in symmetric coordinate storage format, using a conjugate gradient or Lanczos method, without preconditioning, with Jacobi or with SSOR preconditioning.

## 2  Specification

 #include #include
 void nag_sparse_herm_sol (Nag_SparseSym_Method method, Nag_SparseSym_PrecType precon, Integer n, Integer nnz, const Complex a[], const Integer irow[], const Integer icol[], double omega, const Complex b[], double tol, Integer maxitn, Complex x[], double *rnorm, Integer *itn, double rdiag[], NagError *fail)

## 3  Description

nag_sparse_herm_sol (f11jsc) solves a complex sparse Hermitian linear system of equations
 $Ax=b,$
using a preconditioned conjugate gradient method (see Barrett et al. (1994)), or a preconditioned Lanczos method based on the algorithm SYMMLQ (see Paige and Saunders (1975)). The conjugate gradient method is more efficient if $A$ is positive definite, but may fail to converge for indefinite matrices. In this case the Lanczos method should be used instead. For further details see Barrett et al. (1994).
nag_sparse_herm_sol (f11jsc) 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 Cholesky (IC) preconditioning see nag_sparse_herm_chol_sol (f11jqc).
The matrix $A$ is represented in symmetric coordinate storage (SCS) format (see Section 2.1.2 in the f11 Chapter Introduction) in the arrays a, irow and icol. The array a holds the nonzero entries in the lower triangular part of the matrix, while irow and icol hold the corresponding row and column indices.

## 4  References

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
Paige C C and Saunders M A (1975) Solution of sparse indefinite systems of linear equations SIAM J. Numer. Anal. 12 617–629
Young D (1971) Iterative Solution of Large Linear Systems Academic Press, New York

## 5  Arguments

1:     methodNag_SparseSym_MethodInput
On entry: specifies the iterative method to be used.
${\mathbf{method}}=\mathrm{Nag_SparseSym_CG}$
${\mathbf{method}}=\mathrm{Nag_SparseSym_SYMMLQ}$
Lanczos method (SYMMLQ).
Constraint: ${\mathbf{method}}=\mathrm{Nag_SparseSym_CG}$ or $\mathrm{Nag_SparseSym_SYMMLQ}$.
2:     preconNag_SparseSym_PrecTypeInput
On entry: specifies the type of preconditioning to be used.
${\mathbf{precon}}=\mathrm{Nag_SparseSym_NoPrec}$
No preconditioning.
${\mathbf{precon}}=\mathrm{Nag_SparseSym_JacPrec}$
Jacobi.
${\mathbf{precon}}=\mathrm{Nag_SparseSym_SSORPrec}$
Symmetric successive-over-relaxation (SSOR).
Constraint: ${\mathbf{precon}}=\mathrm{Nag_SparseSym_NoPrec}$, $\mathrm{Nag_SparseSym_JacPrec}$ or $\mathrm{Nag_SparseSym_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 lower triangular part of the matrix $A$.
Constraint: $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}+1\right)/2$.
5:     a[nnz]const ComplexInput
On entry: the nonzero elements of the lower triangular part 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_herm_sort (f11zpc) 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 array a.
Constraints:
irow and icol must satisfy these constraints (which may be imposed by a call to nag_sparse_herm_sort (f11zpc)):
• $1\le {\mathbf{irow}}\left[\mathit{i}\right]\le {\mathbf{n}}$ and $1\le {\mathbf{icol}}\left[\mathit{i}\right]\le {\mathbf{irow}}\left[\mathit{i}\right]$, for $\mathit{i}=0,1,\dots ,{\mathbf{nnz}}-1$;
• ${\mathbf{irow}}\left[\mathit{i}-1\right]<{\mathbf{irow}}\left[\mathit{i}\right]$ or ${\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_SparseSym_SSORPrec}$, omega is the relaxation argument $\omega$ to be used in the SSOR method. Otherwise omega need not be initialized.
Constraint: $0.0<{\mathbf{omega}}<2.0$.
9:     b[n]const ComplexInput
On entry: the right-hand side vector $b$.
10:   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$.
11:   maxitnIntegerInput
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxitn}}\ge 1$.
12:   x[n]ComplexInput/Output
On entry: an initial approximation to the solution vector $x$.
On exit: an improved approximation to the solution vector $x$.
13:   rnormdouble *Output
On exit: the final value of the residual norm $‖{r}_{k}‖$, where $k$ is the output value of itn.
14:   itnInteger *Output
On exit: the number of iterations carried out.
15:   rdiag[n]doubleOutput
On exit: the elements of the diagonal matrix ${D}^{-1}$, where $D$ is the diagonal part of $A$. Note that since $A$ is Hermitian the elements of ${D}^{-1}$ are necessarily real.
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 has been achieved and further iterations could not improve the result.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_COEFF_NOT_POS_DEF
The matrix of the coefficients a appears not to be positive definite. The computation cannot continue.
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{nnz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}+1\right)/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.
A serious error, code $〈\mathit{\text{value}}〉$, has occurred in an internal call to nag_sparse_herm_basic_solver (f11gsc). Check all function calls and array sizes. Seek expert help.
A serious error, code $〈\mathit{\text{value}}〉$, has occurred in an internal call to $〈\mathit{\text{value}}〉$. Check all function calls and array sizes. Seek expert help.
NE_INVALID_SCS
On entry, $i=〈\mathit{\text{value}}〉$, ${\mathbf{icol}}\left[i-1\right]=〈\mathit{\text{value}}〉$ and ${\mathbf{irow}}\left[i-1\right]=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{icol}}\left[i-1\right]\ge 1$ and ${\mathbf{icol}}\left[i-1\right]\le {\mathbf{irow}}\left[i-1\right]$.
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}}〉$. Consider calling nag_sparse_herm_sort (f11zpc) to reorder and sum or remove duplicates.
NE_PRECOND_NOT_POS_DEF
The preconditioner appears not to be positive definite. The computation cannot continue.
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 non-real diagonal entry in row $〈\mathit{\text{value}}〉$.
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_herm_sol (f11jsc) for each iteration is roughly proportional to nnz. One iteration with the Lanczos method (SYMMLQ) requires a slightly larger number of operations than one iteration with the conjugate gradient method.
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 matrix of the coefficients $\stackrel{-}{A}={M}^{-1}A$.

## 9  Example

This example solves a complex sparse Hermitian positive definite system of equations using the conjugate gradient method, with SSOR preconditioning.

### 9.1  Program Text

Program Text (f11jsce.c)

### 9.2  Program Data

Program Data (f11jsce.d)

### 9.3  Program Results

Program Results (f11jsce.r)