NAG Library Function Document

nag_sparse_sym_precon_ichol_solve (f11jbc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

+− 9 Further Comments

9.1 Timing

9.2 Use of check

+− 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1 Purpose

nag_sparse_sym_precon_ichol_solve (f11jbc) solves a system of linear equations involving the incomplete Cholesky preconditioning matrix generated by nag_sparse_sym_chol_fac (f11jac).

2 Specification

#include <nag.h>

#include <nagf11.h>

void	nag_sparse_sym_precon_ichol_solve (Integer n, const double a[], Integer la, const Integer irow[], const Integer icol[], const Integer ipiv[], const Integer istr[], Nag_SparseSym_CheckData check, const double y[], double x[], NagError *fail)

3 Description

nag_sparse_sym_precon_ichol_solve (f11jbc) solves a system of linear equations

M x = y

involving the preconditioning matrix

M = P L D L^{T} P^{T}

, corresponding to an incomplete Cholesky decomposition of a sparse symmetric matrix stored in symmetric coordinate storage (SCS) format (see Section 2.1.2 in the f11 Chapter Introduction), as generated by nag_sparse_sym_chol_fac (f11jac).

In the above decomposition

L

is a lower triangular sparse matrix with unit diagonal,

D

is a diagonal matrix and

P

is a permutation matrix.

L

and

D

are supplied to nag_sparse_sym_precon_ichol_solve (f11jbc) through the matrix

C = L + D^{- 1} - I

which is a lower triangular n by n sparse matrix, stored in SCS format, as returned by nag_sparse_sym_chol_fac (f11jac). The permutation matrix

P

is returned from nag_sparse_sym_chol_fac (f11jac) via the array ipiv.

It is envisaged that a common use of nag_sparse_sym_precon_ichol_solve (f11jbc) will be to carry out the preconditioning step required in the application of nag_sparse_sym_basic_solver (f11gec) to sparse symmetric linear systems. nag_sparse_sym_precon_ichol_solve (f11jbc) is used for this purpose by the Black Box function nag_sparse_sym_chol_sol (f11jcc).

nag_sparse_sym_precon_ichol_solve (f11jbc) may also be used in combination with nag_sparse_sym_chol_fac (f11jac) to solve a sparse symmetric positive definite system of linear equations directly (see Section 9.4 in nag_sparse_sym_chol_fac (f11jac)). This use of nag_sparse_sym_precon_ichol_solve (f11jbc) is demonstrated in Section 10.

4 References

None.

5 Arguments

1: n – IntegerInput

On entry:

n

, the order of the matrix

M

. This must be the same value as was supplied in the preceding call to nag_sparse_sym_chol_fac (f11jac).

Constraint:

n \geq 1

2: a[la] – const doubleInput

On entry: the values returned in the array a by a previous call to nag_sparse_sym_chol_fac (f11jac).

3: la – IntegerInput

On entry: the dimension of the arrays a, irow and icol. This must be the same value returned by the preceding call to nag_sparse_sym_chol_fac (f11jac).

4: irow[la] – const IntegerInput

5: icol[la] – const IntegerInput

6: ipiv[n] – const IntegerInput

7: istr[ $n + 1$ ] – const IntegerInput

On entry: the values returned in arrays irow, icol, ipiv and istr by a previous call to nag_sparse_sym_chol_fac (f11jac).

8: check – Nag_SparseSym_CheckDataInput

On entry: specifies whether or not the input data should be checked.

$check = Nag_SparseSym_Check$: Checks are carried out on the values of n, irow, icol, ipiv and istr.
$check = Nag_SparseSym_NoCheck$: No checks are carried out.

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
NE_BAD_PARAM: On entry, argument $⟨value⟩$ had an illegal value.
NE_INT: On entry, $n = ⟨value⟩$ .
Constraint: $n \geq 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_ROWCOL_PIVOT: Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_sym_chol_fac (f11jac) and nag_sparse_sym_precon_ichol_solve (f11jbc).
NE_INVALID_SCS: Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_sym_chol_fac (f11jac) and nag_sparse_sym_precon_ichol_solve (f11jbc).
NE_INVALID_SCS_PRECOND: Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_sym_chol_fac (f11jac) and nag_sparse_sym_precon_ichol_solve (f11jbc).
NE_NOT_STRICTLY_INCREASING: Check that a, irow, icol, ipiv and istr have not been corrupted between calls to nag_sparse_sym_chol_fac (f11jac) and nag_sparse_sym_precon_ichol_solve (f11jbc).

7 Accuracy

The computed solution

x

is the exact solution of a perturbed system of equations

(M + δ M) x = y

, where

|δ M| \leq c (n) ε P |L| |D| |L^{T}| P^{T},

c (n)

is a modest linear function of

n

, and

ε

is the machine precision.

8 Parallelism and Performance

Not applicable.

9 Further Comments

9.1 Timing

The time taken for a call to nag_sparse_sym_precon_ichol_solve (f11jbc) is proportional to the value of nnzc returned from nag_sparse_sym_chol_fac (f11jac).

9.2 Use of check

It is expected that a common use of nag_sparse_sym_precon_ichol_solve (f11jbc) will be to carry out the preconditioning step required in the application of nag_sparse_sym_basic_solver (f11gec) to sparse symmetric linear systems. In this situation nag_sparse_sym_precon_ichol_solve (f11jbc) is likely to be called many times with the same matrix

M

. In the interests of both reliability and efficiency, you are recommended to set

check = Nag_SparseSym_Check

for the first of such calls, and to set

check = Nag_SparseSym_NoCheck

for all subsequent calls.

10 Example

This example reads in a symmetric positive definite sparse matrix

A

and a vector

y

. It then calls nag_sparse_sym_chol_fac (f11jac), with

lfill = -1

and

dtol = 0.0

, to compute the complete Cholesky decomposition of

A

A = P L D L^{T} P^{T} .

Finally it calls nag_sparse_sym_precon_ichol_solve (f11jbc) to solve the system

P L D L^{T} P^{T} x = y .

NAG Library Function Documentnag_sparse_sym_precon_ichol_solve (f11jbc)