f11 Chapter Contents
f11 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_sparse_sym_chol_sol (f11jcc)

## 1  Purpose

nag_sparse_sym_chol_sol (f11jcc) solves a real sparse symmetric 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_sym_chol_sol (Nag_SparseSym_Method method, Integer n, Integer nnz, const double a[], Integer la, const Integer irow[], const Integer icol[], const Integer ipiv[], const Integer istr[], const double b[], double tol, Integer maxitn, double x[], double *rnorm, Integer *itn, Nag_Sparse_Comm *comm, NagError *fail)

## 3  Description

nag_sparse_sym_chol_sol (f11jcc) solves a real sparse symmetric linear system of equations:
 $Ax = b ,$
using a preconditioned conjugate gradient method (Meijerink and Van der Vorst (1977)), or a preconditioned Lanczos method based on the algorithm SYMMLQ (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_sym_chol_sol (f11jcc) uses the incomplete Cholesky factorization determined by nag_sparse_sym_chol_fac (f11jac) as the preconditioning matrix. A call to nag_sparse_sym_chol_sol (f11jcc) must always be preceded by a call to nag_sparse_sym_chol_fac (f11jac). Alternative preconditioners for the same storage scheme are available by calling nag_sparse_sym_sol (f11jec).
The matrix $A$, and the preconditioning matrix $M$, are represented in symmetric coordinate storage (SCS) format (see the f11 Chapter Introduction) in the arrays a, irow and icol, as returned from nag_sparse_sym_chol_fac (f11jac). 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
Salvini S A and Shaw G J (1995) An evaluation of new NAG Library solvers for large sparse symmetric linear systems NAG Technical Report TR1/95

## 5  Arguments

1:    $\mathbf{method}$Nag_SparseSym_MethodInput
On entry: specifies the iterative method to be used.
${\mathbf{method}}=\mathrm{Nag_SparseSym_CG}$
The conjugate gradient method is used.
${\mathbf{method}}=\mathrm{Nag_SparseSym_Lanczos}$
The Lanczos method, SYMMLQ is used.
Constraint: ${\mathbf{method}}=\mathrm{Nag_SparseSym_CG}$ or $\mathrm{Nag_SparseSym_Lanczos}$.
2:    $\mathbf{n}$IntegerInput
On entry: the order of the matrix $A$. This must be the same value as was supplied in the preceding call to nag_sparse_sym_chol_fac (f11jac).
Constraint: ${\mathbf{n}}\ge 1$.
3:    $\mathbf{nnz}$IntegerInput
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_sym_chol_fac (f11jac).
Constraint: $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}+1\right)/2$.
4:    $\mathbf{a}\left[{\mathbf{la}}\right]$const doubleInput
On entry: the values returned in array a by a previous call to nag_sparse_sym_chol_fac (f11jac).
5:    $\mathbf{la}$IntegerInput
On entry: the second dimension of the arrays a, irow and icol.This must be the same value as returned by a previous call to nag_sparse_sym_chol_fac (f11jac).
Constraint: ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
6:    $\mathbf{irow}\left[{\mathbf{la}}\right]$const IntegerInput
7:    $\mathbf{icol}\left[{\mathbf{la}}\right]$const IntegerInput
8:    $\mathbf{ipiv}\left[{\mathbf{n}}\right]$const IntegerInput
9:    $\mathbf{istr}\left[{\mathbf{n}}+1\right]$const IntegerInput
On entry: the values returned in the arrays irow, icol, ipiv and istr by a previous call to nag_sparse_sym_chol_fac (f11jac).
10:  $\mathbf{b}\left[{\mathbf{n}}\right]$const doubleInput
On entry: the right-hand side vector $b$.
11:  $\mathbf{tol}$doubleInput
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:
 $r k ∞ ≤ τ × b ∞ + A ∞ x k ∞ .$
If ${\mathbf{tol}}\le 0.0$, $\tau =\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(\sqrt{\epsilon },\sqrt{{\mathbf{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{{\mathbf{n}}},\epsilon \right)$ is used.
Constraint: ${\mathbf{tol}}<1.0$.
12:  $\mathbf{maxitn}$IntegerInput
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxitn}}\ge 1$.
13:  $\mathbf{x}\left[{\mathbf{n}}\right]$doubleInput/Output
On entry: an initial approximation to the solution vector $x$.
On exit: an improved approximation to the solution vector $x$.
14:  $\mathbf{rnorm}$double *Output
On exit: the final value of the residual norm ${‖{r}_{k}‖}_{\infty }$, where $k$ is the output value of itn.
15:  $\mathbf{itn}$Integer *Output
On exit: the number of iterations carried out.
16:  $\mathbf{comm}$Nag_Sparse_Comm *Input/Output
On entry/exit: a pointer to a structure of type Nag_Sparse_Comm whose members are used by the iterative solver.
17:  $\mathbf{fail}$NagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_2_INT_ARG_LT
On entry, ${\mathbf{la}}=〈\mathit{\text{value}}〉$ while ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{la}}\ge 2×{\mathbf{nnz}}$.
NE_ACC_LIMIT
The required accuracy could not be obtained. However, a reasonable accuracy has been obtained and further iterations cannot improve the result.
NE_ALLOC_FAIL
Dynamic memory allocation failed.
On entry, argument method had an illegal value.
NE_COEFF_NOT_POS_DEF
The matrix of coefficients appears not to be positive definite.
NE_INT_2
On entry, ${\mathbf{nnz}}=〈\mathit{\text{value}}〉$, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}+1\right)/2$.
NE_INT_ARG_LT
On entry, ${\mathbf{maxitn}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{maxitn}}\ge 1$.
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 1$.
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_SCS
The SCS representation of the matrix $A$ is invalid. Check that the call to nag_sparse_sym_chol_sol (f11jcc) has been preceded by a valid call to nag_sparse_sym_chol_fac (f11jac), and that the arrays a, irow and icol have not been corrupted between the two calls.
NE_INVALID_SCS_PRECOND
The SCS representation of the preconditioning matrix $M$ is invalid. Check that the call to nag_sparse_sym_chol_sol (f11jcc) has been preceded by a valid call to nag_sparse_sym_chol_fac (f11jac), and that the arrays a, irow, icol, ipiv and istr have not been corrupted between the two calls.
NE_NOT_REQ_ACC
The required accuracy has not been obtained in maxitn iterations.
NE_PRECOND_NOT_POS_DEF
The preconditioner appears not to be positive definite.
NE_REAL_ARG_GE
On entry, tol must not be greater than or equal to 1.0: ${\mathbf{tol}}=〈\mathit{\text{value}}〉$.

## 7  Accuracy

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

## 8  Parallelism and Performance

Not applicable.

The time taken by nag_sparse_sym_chol_sol (f11jcc) for each iteration is roughly proportional to the value of nnzc returned from the preceding call to nag_sparse_sym_chol_fac (f11jac). 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 be easily 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$.
Some illustrations of the application of nag_sparse_sym_chol_sol (f11jcc) to linear systems arising from the discretization of two-dimensional elliptic partial differential equations, and to random-valued randomly structured symmetric positive definite linear systems, can be found in Salvini and Shaw (1995).

## 10  Example

This example program solves a symmetric positive definite system of equations using the conjugate gradient method, with incomplete Cholesky preconditioning.

### 10.1  Program Text

Program Text (f11jcce.c)

### 10.2  Program Data

Program Data (f11jcce.d)

### 10.3  Program Results

Program Results (f11jcce.r)