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

Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_sparse_direct_real_gen_refine (f11mh)

Purpose

nag_sparse_direct_real_gen_refine (f11mh) returns error bounds for the solution of a real sparse system of linear equations with multiple right-hand sides, $AX=B$ or ${A}^{\mathrm{T}}X=B$. It improves the solution by iterative refinement in standard precision, in order to reduce the backward error as much as possible.

Syntax

[x, ferr, berr, ifail] = f11mh(trans, icolzp, irowix, a, iprm, il, lval, iu, uval, b, x, 'n', n, 'nrhs_p', nrhs_p)
[x, ferr, berr, ifail] = nag_sparse_direct_real_gen_refine(trans, icolzp, irowix, a, iprm, il, lval, iu, uval, b, x, 'n', n, 'nrhs_p', nrhs_p)

Description

nag_sparse_direct_real_gen_refine (f11mh) returns the backward errors and estimated bounds on the forward errors for the solution of a real system of linear equations with multiple right-hand sides $AX=B$ or ${A}^{\mathrm{T}}X=B$. The function handles each right-hand side vector (stored as a column of the matrix $B$) independently, so we describe the function of nag_sparse_direct_real_gen_refine (f11mh) in terms of a single right-hand side $b$ and solution $x$.
Given a computed solution $x$, the function computes the component-wise backward error $\beta$. This is the size of the smallest relative perturbation in each element of $A$ and $b$ such that if $x$ is the exact solution of a perturbed system:
 $A+δA x = b + δ b then δaij ≤ β aij and δbi ≤ β bi .$
Then the function estimates a bound for the component-wise forward error in the computed solution, defined by:
 $maxi xi - x^i / maxi xi$
where $\stackrel{^}{x}$ is the true solution.
The function uses the $LU$ factorization ${P}_{r}A{P}_{c}=LU$ computed by nag_sparse_direct_real_gen_lu (f11me) and the solution computed by nag_sparse_direct_real_gen_solve (f11mf).

References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

Parameters

Compulsory Input Parameters

1:     $\mathrm{trans}$ – string (length ≥ 1)
Specifies whether $AX=B$ or ${A}^{\mathrm{T}}X=B$ is solved.
${\mathbf{trans}}=\text{'N'}$
$AX=B$ is solved.
${\mathbf{trans}}=\text{'T'}$
${A}^{\mathrm{T}}X=B$ is solved.
Constraint: ${\mathbf{trans}}=\text{'N'}$ or $\text{'T'}$.
2:     $\mathrm{icolzp}\left(:\right)$int64int32nag_int array
The dimension of the array icolzp must be at least ${\mathbf{n}}+1$
${\mathbf{icolzp}}\left(i\right)$ contains the index in $A$ of the start of a new column. See Compressed column storage (CCS) format in the F11 Chapter Introduction.
3:     $\mathrm{irowix}\left(:\right)$int64int32nag_int array
The dimension of the array irowix must be at least ${\mathbf{icolzp}}\left({\mathbf{n}}+1\right)-1$, the number of nonzeros of the sparse matrix $A$
The row index array of sparse matrix $A$.
4:     $\mathrm{a}\left(:\right)$ – double array
The dimension of the array a must be at least ${\mathbf{icolzp}}\left({\mathbf{n}}+1\right)-1$, the number of nonzeros of the sparse matrix $A$
The array of nonzero values in the sparse matrix $A$.
5:     $\mathrm{iprm}\left(7×{\mathbf{n}}\right)$int64int32nag_int array
The column permutation which defines ${P}_{c}$, the row permutation which defines ${P}_{r}$, plus associated data structures as computed by nag_sparse_direct_real_gen_lu (f11me).
6:     $\mathrm{il}\left(:\right)$int64int32nag_int array
The dimension of the array il must be at least as large as the dimension of the array of the same name in nag_sparse_direct_real_gen_lu (f11me)
Records the sparsity pattern of matrix $L$ as computed by nag_sparse_direct_real_gen_lu (f11me).
7:     $\mathrm{lval}\left(:\right)$ – double array
The dimension of the array lval must be at least as large as the dimension of the array of the same name in nag_sparse_direct_real_gen_lu (f11me)
Records the nonzero values of matrix $L$ and some nonzero values of matrix $U$ as computed by nag_sparse_direct_real_gen_lu (f11me).
8:     $\mathrm{iu}\left(:\right)$int64int32nag_int array
The dimension of the array iu must be at least as large as the dimension of the array of the same name in nag_sparse_direct_real_gen_lu (f11me)
Records the sparsity pattern of matrix $U$ as computed by nag_sparse_direct_real_gen_lu (f11me).
9:     $\mathrm{uval}\left(:\right)$ – double array
The dimension of the array uval must be at least as large as the dimension of the array of the same name in nag_sparse_direct_real_gen_lu (f11me)
Records some nonzero values of matrix $U$ as computed by nag_sparse_direct_real_gen_lu (f11me).
10:   $\mathrm{b}\left(\mathit{ldb},:\right)$ – double array
The first dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{nrhs_p}}\right)$.
The $n$ by $\mathit{nrhs}$ right-hand side matrix $B$.
11:   $\mathrm{x}\left(\mathit{ldx},:\right)$ – double array
The first dimension of the array x must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array x must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{nrhs_p}}\right)$.
The $n$ by $\mathit{nrhs}$ solution matrix $X$, as returned by nag_sparse_direct_real_gen_solve (f11mf).

Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the first dimension of the arrays b, x. (An error is raised if these dimensions are not equal.)
$n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 0$.
2:     $\mathrm{nrhs_p}$int64int32nag_int scalar
Default: the second dimension of the arrays b, x.
$\mathit{nrhs}$, the number of right-hand sides in $B$.
Constraint: ${\mathbf{nrhs_p}}\ge 0$.

Output Parameters

1:     $\mathrm{x}\left(\mathit{ldx},:\right)$ – double array
The first dimension of the array x will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array x will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{nrhs_p}}\right)$.
The $n$ by $\mathit{nrhs}$ improved solution matrix $X$.
2:     $\mathrm{ferr}\left({\mathbf{nrhs_p}}\right)$ – double array
${\mathbf{ferr}}\left(\mathit{j}\right)$ contains an estimated error bound for the $\mathit{j}$th solution vector, that is, the $\mathit{j}$th column of $X$, for $\mathit{j}=1,2,\dots ,\mathit{nrhs}$.
3:     $\mathrm{berr}\left({\mathbf{nrhs_p}}\right)$ – double array
${\mathbf{berr}}\left(\mathit{j}\right)$ contains the component-wise backward error bound $\beta$ for the $\mathit{j}$th solution vector, that is, the $\mathit{j}$th column of $X$, for $\mathit{j}=1,2,\dots ,\mathit{nrhs}$.
4:     $\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$
Constraint: $\mathit{ldb}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
Constraint: $\mathit{ldx}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
Constraint: ${\mathbf{n}}\ge 0$.
Constraint: ${\mathbf{nrhs_p}}\ge 0$.
On entry, ${\mathbf{trans}}=_$.
Constraint: ${\mathbf{trans}}=\text{'N'}$ or $\text{'T'}$.
${\mathbf{ifail}}=2$
Incorrect row permutations in array iprm.
${\mathbf{ifail}}=3$
Incorrect column permutations in array iprm.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

Accuracy

The bounds returned in ferr are not rigorous, because they are estimated, not computed exactly; but in practice they almost always overestimate the actual error.

At most five steps of iterative refinement are performed, but usually only one or two steps are required.
Estimating the forward error involves solving a number of systems of linear equations of the form $Ax=b$ or ${A}^{\mathrm{T}}x=b$;

Example

This example solves the system of equations $AX=B$ using iterative refinement and to compute the forward and backward error bounds, where
 $A= 2.00 1.00 0 0 0 0 0 1.00 -1.00 0 4.00 0 1.00 0 1.00 0 0 0 1.00 2.00 0 -2.00 0 0 3.00 and B= 1.56 3.12 -0.25 -0.50 3.60 7.20 1.33 2.66 0.52 1.04 .$
Here $A$ is nonsymmetric and must first be factorized by nag_sparse_direct_real_gen_lu (f11me).
```function f11mh_example

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

% Solve AX=B for sparse A

% A and B
n      = int64(5);
nz     = int64(11);
icolzp = [int64(1); 3; 5;  7; 9; 12];
irowix = [int64(1); 3; 1;  5; 2;  3;  2; 4; 3; 4; 5];
a      = [        2;  4; 1; -2; 1;  1; -1; 1; 1; 2; 3];
b = [  1.56,  3.12;
-0.25, -0.50;
3.60,  7.20;
1.33,  2.66;
0.52,  1.04];

% Calculate COLAMD permutation
spec = 'M';
iprm = zeros(1, 7*n, 'int64');

[iprm, ifail] = f11md( ...
spec, n, icolzp, irowix, iprm);

% Factorise
thresh = 1;
nzlmx  = int64(8*nz);
nzlumx = int64(8*nz);
nzumx  = int64(8*nz);

[iprm, nzlumx, il, lval, iu, uval, nnzl, nnzu, flop, ifail] = ...
f11me( ...
n, irowix, a, iprm, thresh, nzlmx, nzlumx, nzumx);

% Compute solution in x
x     = b;
trans = 'N';

[x, ifail] = f11mf( ...
trans, iprm, il, lval, iu, uval, x);

% Improve solution, and compute backward errors and estimated
% bounds on the forward errors
[x, ferr, berr, ifail] = ...
f11mh( ...
trans, icolzp, irowix, a, iprm, il, lval, iu, uval, b, x);

fprintf('Solutions:\n');
disp(x);
fprintf('Estmated Forward Error:\n');
fprintf('%8.1e\n', ferr);
fprintf('\nEstmated Backward Error:\n');
fprintf('%8.1e\n', berr);

```
```f11mh example results

Solutions:
0.7000    1.4000
0.1600    0.3200
0.5200    1.0400
0.7700    1.5400
0.2800    0.5600

Estmated Forward Error:
5.0e-15
5.0e-15

Estmated Backward Error:
3.6e-17
3.6e-17
```