f11 Chapter Contents
f11 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_sparse_herm_chol_sol (f11jqc)

## 1  Purpose

nag_sparse_herm_chol_sol (f11jqc) solves a complex sparse Hermitian system of linear equations, represented in symmetric coordinate storage format, using a conjugate gradient or Lanczos method, with incomplete Cholesky preconditioning.

## 2  Specification

 #include #include
 void nag_sparse_herm_chol_sol (Nag_SparseSym_Method method, Integer n, Integer nnz, const Complex a[], Integer la, const Integer irow[], const Integer icol[], const Integer ipiv[], const Integer istr[], const Complex b[], double tol, Integer maxitn, Complex x[], double *rnorm, Integer *itn, NagError *fail)

## 3  Description

nag_sparse_herm_chol_sol (f11jqc) solves a complex sparse Hermitian linear system of equations
 $Ax=b,$
using a preconditioned conjugate gradient method (see Meijerink and Van der Vorst (1977)), 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_chol_sol (f11jqc) uses the incomplete Cholesky factorization determined by nag_sparse_herm_chol_fac (f11jnc) as the preconditioning matrix. A call to nag_sparse_herm_chol_sol (f11jqc) must always be preceded by a call to nag_sparse_herm_chol_fac (f11jnc). Alternative preconditioners for the same storage scheme are available by calling nag_sparse_herm_sol (f11jsc).
The matrix $A$ and the preconditioning matrix $M$ are represented in symmetric coordinate storage (SCS) format (see Section 2.1.2 in the f11 Chapter Introduction) in the arrays a, irow and icol, as returned from nag_sparse_herm_chol_fac (f11jnc). The array a holds the nonzero entries in the lower triangular parts of these matrices, 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
Meijerink J and Van der Vorst H (1977) An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix Math. Comput. 31 148–162
Paige C C and Saunders M A (1975) Solution of sparse indefinite systems of linear equations SIAM J. Numer. Anal. 12 617–629

## 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:     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_herm_chol_fac (f11jnc).
Constraint: ${\mathbf{n}}\ge 1$.
3:     nnzIntegerInput
On entry: the number of nonzero elements in the lower triangular part of the matrix $A$. This must be the same value as was supplied in the preceding call to nag_sparse_herm_chol_fac (f11jnc).
Constraint: $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}+1\right)/2$.
4:     a[la]const ComplexInput
On entry: the values returned in the array a by a previous call to nag_sparse_herm_chol_fac (f11jnc).
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_herm_chol_fac (f11jnc).
Constraint: ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
6:     irow[la]const IntegerInput
7:     icol[la]const IntegerInput
8:     ipiv[n]const IntegerInput
9:     istr[${\mathbf{n}}+1$]const IntegerInput
On entry: the values returned in arrays irow, icol, ipiv and istr by a previous call to nag_sparse_herm_chol_fac (f11jnc).
10:   b[n]const ComplexInput
On entry: the right-hand side vector $b$.
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 has been achieved.
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{la}}=〈\mathit{\text{value}}〉$ and ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
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}}〉$, ${\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]$.
Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_herm_chol_fac (f11jnc) and nag_sparse_herm_chol_sol (f11jqc).
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, ipiv and istr have not been corrupted between calls to nag_sparse_herm_chol_fac (f11jnc) and nag_sparse_herm_chol_sol (f11jqc).
NE_INVALID_SCS_PRECOND
The SCS representation of the preconditioner is invalid. Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_herm_chol_fac (f11jnc) and nag_sparse_herm_chol_sol (f11jqc).
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, ipiv and istr have not been corrupted between calls to nag_sparse_herm_chol_fac (f11jnc) and nag_sparse_herm_chol_sol (f11jqc).
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, ipiv and istr have not been corrupted between calls to nag_sparse_herm_chol_fac (f11jnc) and nag_sparse_herm_chol_sol (f11jqc).
NE_PRECOND_NOT_POS_DEF
The preconditioner appears not to be positive definite. The computation cannot continue.
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_herm_chol_sol (f11jqc) for each iteration is roughly proportional to the value of nnzc returned from the preceding call to nag_sparse_herm_chol_fac (f11jnc). 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 incomplete Cholesky preconditioning.

### 9.1  Program Text

Program Text (f11jqce.c)

### 9.2  Program Data

Program Data (f11jqce.d)

### 9.3  Program Results

Program Results (f11jqce.r)