Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_sparse_real_gen_precon_ssor_solve (f11dd)

## Purpose

nag_sparse_real_gen_precon_ssor_solve (f11dd) 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.

## Syntax

[x, ifail] = f11dd(trans, a, irow, icol, rdiag, omega, check, y, 'n', n, 'nz', nz)
[x, ifail] = nag_sparse_real_gen_precon_ssor_solve(trans, a, irow, icol, rdiag, omega, check, y, 'n', n, 'nz', nz)

## Description

nag_sparse_real_gen_precon_ssor_solve (f11dd) solves a system of linear equations
 $Mx=y, or MTx=y,$
according to the value of the argument trans, where the matrix
 $M=1ω2-ω D+ω L D-1 D+ω U$
corresponds to symmetric successive-over-relaxation (SSOR) (see Young (1971)) applied to a linear system $Ax=b$, where $A$ is a real sparse nonsymmetric matrix stored in coordinate storage (CS) format (see Coordinate storage (CS) format 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 $\omega$ is a user-defined relaxation parameter.
It is envisaged that a common use of nag_sparse_real_gen_precon_ssor_solve (f11dd) will be to carry out the preconditioning step required in the application of nag_sparse_real_gen_basic_solver (f11be) to sparse linear systems. For an illustration of this use of nag_sparse_real_gen_precon_ssor_solve (f11dd) see the example program given in Example. nag_sparse_real_gen_precon_ssor_solve (f11dd) is also used for this purpose by the Black Box function nag_sparse_real_gen_solve_jacssor (f11de).

## References

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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{trans}$ – string (length ≥ 1)
Specifies whether or not the matrix $M$ is transposed.
${\mathbf{trans}}=\text{'N'}$
$Mx=y$ is solved.
${\mathbf{trans}}=\text{'T'}$
${M}^{\mathrm{T}}x=y$ is solved.
Constraint: ${\mathbf{trans}}=\text{'N'}$ or $\text{'T'}$.
2:     $\mathrm{a}\left({\mathbf{nz}}\right)$ – double array
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_real_gen_sort (f11za) may be used to order the elements in this way.
3:     $\mathrm{irow}\left({\mathbf{nz}}\right)$int64int32nag_int array
4:     $\mathrm{icol}\left({\mathbf{nz}}\right)$int64int32nag_int array
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_real_gen_sort (f11za)):
• $1\le {\mathbf{irow}}\left(\mathit{i}\right)\le {\mathbf{n}}$ and $1\le {\mathbf{icol}}\left(\mathit{i}\right)\le {\mathbf{n}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{nz}}$;
• either ${\mathbf{irow}}\left(\mathit{i}-1\right)<{\mathbf{irow}}\left(\mathit{i}\right)$ or both ${\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}=2,3,\dots ,{\mathbf{nz}}$.
5:     $\mathrm{rdiag}\left({\mathbf{n}}\right)$ – double array
The elements of the diagonal matrix ${D}^{-1}$, where $D$ is the diagonal part of $A$.
6:     $\mathrm{omega}$ – double scalar
The relaxation parameter $\omega$.
Constraint: $0.0<{\mathbf{omega}}<2.0$.
7:     $\mathrm{check}$ – string (length ≥ 1)
Specifies whether or not the CS representation of the matrix $M$ should be checked.
${\mathbf{check}}=\text{'C'}$
Checks are carried on the values of n, nz, irow, icol and omega.
${\mathbf{check}}=\text{'N'}$
None of these checks are carried out.
Constraint: ${\mathbf{check}}=\text{'C'}$ or $\text{'N'}$.
8:     $\mathrm{y}\left({\mathbf{n}}\right)$ – double array
The right-hand side vector $y$.

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the arrays rdiag, y. (An error is raised if these dimensions are not equal.)
$n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 1$.
2:     $\mathrm{nz}$int64int32nag_int scalar
Default: the dimension of the arrays a, irow, icol. (An error is raised if these dimensions are not equal.)
The number of nonzero elements in the matrix $A$.
Constraint: $1\le {\mathbf{nz}}\le {{\mathbf{n}}}^{2}$.

### Output Parameters

1:     $\mathrm{x}\left({\mathbf{n}}\right)$ – double array
The solution vector $x$.
2:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\mathbf{ifail}}=1$
 On entry, ${\mathbf{trans}}\ne \text{'N'}$ or $\text{'T'}$, or ${\mathbf{check}}\ne \text{'C'}$ or $\text{'N'}$.
${\mathbf{ifail}}=2$
 On entry, ${\mathbf{n}}<1$, or ${\mathbf{nz}}<1$, or ${\mathbf{nz}}>{{\mathbf{n}}}^{2}$, or omega lies outside the interval $\left(0.0,2.0\right)$,
${\mathbf{ifail}}=3$
On entry, the arrays irow and icol fail to satisfy the following constraints:
• $1\le {\mathbf{irow}}\left(\mathit{i}\right)\le {\mathbf{n}}$ and $1\le {\mathbf{icol}}\left(\mathit{i}\right)\le {\mathbf{n}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{nz}}$;
• ${\mathbf{irow}}\left(i-1\right)<{\mathbf{irow}}\left(i\right)$ or ${\mathbf{irow}}\left(i-1\right)={\mathbf{irow}}\left(i\right)$ and ${\mathbf{icol}}\left(i-1\right)<{\mathbf{icol}}\left(i\right)$, for $i=2,3,\dots ,{\mathbf{nz}}$.
Therefore a nonzero element has been supplied which does not lie in the matrix $A$, is out of order, or has duplicate row and column indices. Call nag_sparse_real_gen_sort (f11za) to reorder and sum or remove duplicates.
${\mathbf{ifail}}=4$
On entry, the matrix $A$ has a zero diagonal element. The SSOR preconditioner is not appropriate for this problem.
${\mathbf{ifail}}=-99$
An unexpected error has been triggered by this routine. Please contact NAG.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## Accuracy

If ${\mathbf{trans}}=\text{'N'}$ the computed solution $x$ is the exact solution of a perturbed system of equations $\left(M+\delta M\right)x=y$, where
 $δM≤cnεD+ωLD-1D+ωU,$
$c\left(n\right)$ is a modest linear function of $n$, and $\epsilon$ is the machine precision. An equivalent result holds when ${\mathbf{trans}}=\text{'T'}$.

### Timing

The time taken for a call to nag_sparse_real_gen_precon_ssor_solve (f11dd) is proportional to nz.

### Use of check

It is expected that a common use of nag_sparse_real_gen_precon_ssor_solve (f11dd) will be to carry out the preconditioning step required in the application of nag_sparse_real_gen_basic_solver (f11be) to sparse linear systems. In this situation nag_sparse_real_gen_precon_ssor_solve (f11dd) 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 ${\mathbf{check}}=\text{'C'}$ for the first of such calls, and for all subsequent calls set ${\mathbf{check}}=\text{'N'}$.

## Example

This example solves a sparse linear system of equations:
 $Ax=b,$
using RGMRES with SSOR preconditioning.
The RGMRES algorithm itself is implemented by the reverse communication function nag_sparse_real_gen_basic_solver (f11be), 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 ${\mathbf{irevcm}}=1$, a matrix-vector product $v=Au$ is required. This is implemented by a call to nag_sparse_real_gen_matvec (f11xa).
• If ${\mathbf{irevcm}}=-1$, a transposed matrix-vector product $v={A}^{\mathrm{T}}u$ is required in the estimation of the norm of $A$. This is implemented by a call to nag_sparse_real_gen_matvec (f11xa).
• If ${\mathbf{irevcm}}=2$, a solution of the preconditioning equation $Mv=u$ is required. This is achieved by a call to nag_sparse_real_gen_precon_ssor_solve (f11dd).
• If ${\mathbf{irevcm}}=4$, nag_sparse_real_gen_basic_solver (f11be) 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_real_gen_basic_solver (f11be).
```function f11dd_example

fprintf('f11dd example results\n\n');

% Sparse matrix A
n    = int64(5);
m    = int64(2);
nz   = int64(16);
a    = zeros(3*nz, 1);
irow = zeros(3*nz, 1, 'int64');
icol = irow;
a(1:nz)    = [2; 1;-1;-3;-2; 1; 1; 5; 3; 1;-2;-3;-1; 4;-2;-6];
irow(1:nz) = [1; 1; 1; 2; 2; 2; 3; 3; 3; 3; 4; 4; 4; 5; 5; 5];
icol(1:nz) = [1; 2; 4; 2; 3; 5; 1; 3; 4; 5; 1; 4; 5; 2; 3; 5];

% Solver setup initializations
method = 'rgmres';
precon = 'P';
tol    = 1e-10;
maxitn = int64(1000);
anorm  = 0;
sigmax = 0;
monit  = int64(0);
lwork  = max([n*(m+3)+m*(m+5)+101,7*n+100,(2*n+m)*(m+2)+n+100,10*n+100]);

% Initialize solver
[lwreq, work, ifail] = ...
f11bd( ...
method, precon, n, m, tol, maxitn, anorm, sigmax, monit, lwork, ...
'norm_p', 'I');

% RHS b and initial guess x
b = [0; -7; 33; -19; -28];
x = zeros(n, 1);

% Calculate reciprocal diagonal matrix elements for SSOR preconditioning
rdiag = zeros(n, 1);
if strcmpi(precon, 'P')
dcount = zeros(n, 1, 'int64');

for i = 1:nz
if irow(i) == icol(i)
dcount(irow(i)) = dcount(irow(i)) + 1;
if a(i) ~= 0
rdiag(irow(i)) = 1/a(i);
else
error('Matrix has a zero diagonal element');
end
end
end

for i = 1:n
if dcount(i) == 0
error('Matrix has a missing diagonal element');
elseif dcount(i) >= 2
error('Matrix has a multiple diagonal element');
end
end
end
% Preconditioner input argument initializations
trans  = 'N';
omega  = 1.1;
ckddf = 'C';

% Solver input argument initialization
irevcm = int64(0);
wgt = zeros(n, 1);

% Matrix-vector input argument
ckxaf = 'C';

% Solve the linear system by reverse communication
while irevcm ~= 4
[irevcm, x, b, work, ifail] = f11be( ...
irevcm, x, b, wgt, work);

if (irevcm == -1)
% Compute transposed matrix-vector product
[b, ifail] = f11xa( ...
'T', a(1:nz), irow(1:nz), icol(1:nz), ckxaf, x);
ckxaf = 'N';
elseif (irevcm == 1)
% Compute matrix-vector product
[b, ifail] = f11xa( ...
'N', a(1:nz), irow(1:nz), icol(1:nz), ckxaf, x);
ckxaf = 'N';
elseif (irevcm == 2)
% SSOR preconditioning
[b, ifail] = f11dd( ...
trans, a(1:nz), irow(1:nz), icol(1:nz), rdiag,...
omega, ckddf, x);
ckddf = 'N';
end
end

% Get information about the computation
[itn, stplhs, stprhs, anorm, sigmax, ifail] = ...
f11bf(work);
fprintf('\nConverged in %d iterations\n', itn);
fprintf('Matrix norm         = %16.3e\n', anorm);
fprintf('Final residual norm = %16.3e\n\n', stplhs);
disp('Solution');
disp(x);

```
```f11dd example results

Converged in 12 iterations
Matrix norm         =        1.200e+01
Final residual norm =        3.841e-09

Solution
1.0000
2.0000
3.0000
4.0000
5.0000

```

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015