NAG Library Function Document

nag_sparse_nsym_precon_ssor_solve (f11ddc)

+− 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_nsym_precon_ssor_solve (f11ddc) solves a system of linear equations involving the preconditioning matrix corresponding to SSOR applied to a real sparse nonsymmetric matrix, represented in coordinate storage format.

2 Specification

#include <nag.h>

#include <nagf11.h>

void	nag_sparse_nsym_precon_ssor_solve (Nag_TransType trans, Integer n, Integer nnz, const double a[], const Integer irow[], const Integer icol[], const double rdiag[], double omega, Nag_SparseNsym_CheckData check, const double y[], double x[], NagError *fail)

3 Description

nag_sparse_nsym_precon_ssor_solve (f11ddc) solves a system of linear equations

\begin{matrix} M x = y, & or & M^{T} x = y, \end{matrix}

according to the value of the argument trans, where the matrix

M = \frac{1}{ω (2 - ω)} (D + ω L) D^{- 1} (D + ω U)

corresponds to symmetric successive-over-relaxation (SSOR) (see Young (1971)) applied to a linear system

A x = b

, where

A

is a real sparse nonsymmetric matrix stored in coordinate storage (CS) format (see Section 2.1.1 in the f11 Chapter Introduction).

In the definition of

M

given above

D

is the diagonal part of

A

L

is the strictly lower triangular part of

A

U

is the strictly upper triangular part of

A

, and

ω

is a user-defined relaxation argument.

It is envisaged that a common use of nag_sparse_nsym_precon_ssor_solve (f11ddc) will be to carry out the preconditioning step required in the application of nag_sparse_nsym_basic_solver (f11bec) to sparse linear systems. For an illustration of this use of nag_sparse_nsym_precon_ssor_solve (f11ddc) see the example program given in Section 10. nag_sparse_nsym_precon_ssor_solve (f11ddc) is also used for this purpose by the Black Box function nag_sparse_nsym_sol (f11dec).

4 References

Young D (1971) Iterative Solution of Large Linear Systems Academic Press, New York

5 Arguments

1: trans – Nag_TransTypeInput

On entry: specifies whether or not the matrix

M

is transposed.

$trans = Nag_NoTrans$: $M x = y$ is solved.
$trans = Nag_Trans$: $M^{T} x = y$ is solved.

Constraint:

trans = Nag_NoTrans

Nag_Trans

2: n – IntegerInput

On entry:

n

, the order of the matrix

A

Constraint:

n \geq 1

3: nnz – IntegerInput

On entry: the number of nonzero elements in the matrix

A

Constraint:

1 \leq nnz \leq n^{2}

4: a[nnz] – const doubleInput

On entry: the nonzero elements in 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_nsym_sort (f11zac) may be used to order the elements in this way.

5: irow[nnz] – const IntegerInput

6: 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 the following constraints (which may be imposed by a call to nag_sparse_nsym_sort (f11zac)):

$1 \leq irow [i] \leq n$ and $1 \leq icol [i] \leq n$ , for $i = 0, 1, \dots, nnz - 1$ ;
either $irow [i - 1] < irow [i]$ or both $irow [i - 1] = irow [i]$ and $icol [i - 1] < icol [i]$ , for $i = 1, 2, \dots, nnz - 1$ .

7: rdiag[n] – const doubleInput

On entry: the elements of the diagonal matrix

D^{- 1}

, where

D

is the diagonal part of

A

8: omega – doubleInput

On entry: the relaxation argument

ω

Constraint:

0.0 < omega < 2.0

9: check – Nag_SparseNsym_CheckDataInput

On entry: specifies whether or not the CS representation of the matrix

M

should be checked.

$check = Nag_SparseNsym_Check$: Checks are carried on the values of n, nnz, irow, icol and omega.
$check = Nag_SparseNsym_NoCheck$: None of these 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$ .
On entry, $nnz = ⟨value⟩$ .
Constraint: $1 \leq nnz \leq n^{2}$ .
NE_INT_2: On entry, $nnz = ⟨value⟩$ and $n = ⟨value⟩$ .
Constraint: $1 \leq nnz \leq n^{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.
NE_INVALID_CS: On entry, $i = ⟨value⟩$ , $icol [i - 1] = ⟨value⟩$ and $n = ⟨value⟩$ .
Constraint: $icol [i - 1] \geq 1$ and $icol [i - 1] \leq n$ .
On entry, $i = ⟨value⟩$ , $irow [i - 1] = ⟨value⟩$ and $n = ⟨value⟩$ .
Constraint: $irow [i - 1] \geq 1$ and $irow [i - 1] \leq n$ .
NE_NOT_STRICTLY_INCREASING: On entry, $a [i - 1]$ is out of order: $i = ⟨value⟩$ .
On entry, the location ( $irow [I - 1], icol [I - 1]$ ) is a duplicate: $I = ⟨value⟩$ .
NE_REAL: On entry, $omega = ⟨value⟩$ .
Constraint: $0.0 < omega < 2.0$ .
NE_ZERO_DIAG_ELEM: The matrix $A$ has no diagonal entry in row $⟨value⟩$ .

7 Accuracy

trans = Nag_NoTrans

the computed solution

x

is the exact solution of a perturbed system of equations

(M + δ M) x = y

, where

|δ M| \leq c (n) ε |D + ω L| |D^{- 1}| |D + ω U|,

c (n)

is a modest linear function of

n

, and

ε

is the machine precision. An equivalent result holds when

trans = Nag_Trans

8 Parallelism and Performance

Not applicable.

9 Further Comments

9.1 Timing

The time taken for a call to nag_sparse_nsym_precon_ssor_solve (f11ddc) is proportional to nnz.

9.2 Use of check

It is expected that a common use of nag_sparse_nsym_precon_ssor_solve (f11ddc) will be to carry out the preconditioning step required in the application of nag_sparse_nsym_basic_solver (f11bec) to sparse linear systems. In this situation nag_sparse_nsym_precon_ssor_solve (f11ddc) 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_SparseNsym_Check

for the first of such calls, and for all subsequent calls set

check = Nag_SparseNsym_NoCheck

10 Example

This example solves a sparse linear system of equations:

A x = b,

using RGMRES with SSOR preconditioning.

The RGMRES algorithm itself is implemented by the reverse communication function nag_sparse_nsym_basic_solver (f11bec), which returns repeatedly to the calling program with various values of the argument irevcm. This argument indicates the action to be taken by the calling program.

If $irevcm = 1$ , a matrix-vector product $v = A u$ is required. This is implemented by a call to nag_sparse_nsym_matvec (f11xac).
If $irevcm = -1$ , a transposed matrix-vector product $v = A^{T} u$ is required in the estimation of the norm of $A$ . This is implemented by a call to nag_sparse_nsym_matvec (f11xac).
If $irevcm = 2$ , a solution of the preconditioning equation $M v = u$ is required. This is achieved by a call to nag_sparse_nsym_precon_ssor_solve (f11ddc).
If $irevcm = 4$ , nag_sparse_nsym_basic_solver (f11bec) has completed its tasks. Either the iteration has terminated, or an error condition has arisen.

For further details see the function document for nag_sparse_nsym_basic_solver (f11bec).

NAG Library Function Documentnag_sparse_nsym_precon_ssor_solve (f11ddc)

+− 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

NAG Library Function Document

nag_sparse_nsym_precon_ssor_solve (f11ddc)