hide long namesshow long names
hide short namesshow short names
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_sym_rcm (f11ye)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

nag_sparse_sym_rcm (f11ye) reduces the bandwidth of a sparse symmetric matrix stored in compressed column storage format using the Reverse Cuthill–McKee algorithm.

Syntax

[perm, info, ifail] = f11ye(icolzp, irowix, lopts, mask, 'n', n, 'nz', nz)
[perm, info, ifail] = nag_sparse_sym_rcm(icolzp, irowix, lopts, mask, 'n', n, 'nz', nz)

Description

nag_sparse_sym_rcm (f11ye) takes the compressed column storage (CCS) representation (see Compressed column storage (CCS) format in the F11 Chapter Introduction) of an n by n symmetric matrix A and applies the Reverse Cuthill–McKee (RCM) algorithm which aims to minimize the bandwidth of the matrix A by reordering the rows and columns symmetrically. This also results in a lower profile of the matrix (see Further Comments).
nag_sparse_sym_rcm (f11ye) can be useful for solving systems of equations Ax=b, as the permuted system PAPTPx=Pb (where P is the permutation matrix described by the vector perm returned by nag_sparse_sym_rcm (f11ye)) may require less storage space and/or less computational steps when solving (see Wai-Hung and Sherman (1976)).
nag_sparse_sym_rcm (f11ye) may be used prior to nag_sparse_real_symm_precon_ichol (f11ja) and nag_sparse_real_symm_precon_ichol_solve (f11jb) (see Example in nag_sparse_real_symm_precon_ichol_solve (f11jb)).

References

Pissanetsky S (1984) Sparse Matrix Technology Academic Press
Wai-Hung L and Sherman A H (1976) Comparative analysis of the Cuthill–McKee and the reverse Cuthill–McKee ordering algorithms for sparse matrices SIAM J. Numer. Anal. 13(2) 198–213

Parameters

Compulsory Input Parameters

1:     icolzpn+1 int64int32nag_int array
icolzp records the index into irowix which starts each new column.
Constraints:
  • 1icolzpinz+1, for i=2,3,,n;
  • icolzp1=1;
  • icolzpn+1=nz+1, where icolzpi holds the position integer for the starts of the columns in irowix.
2:     irowixnz int64int32nag_int array
The row indices corresponding to the nonzero elements in the matrix A.
Constraint: 1irowixin, for i=1,2,,nz.
3:     lopts5 – logical array
The options to be used by nag_sparse_sym_rcm (f11ye).
lopts1=true
Row/column i of the matrix A will only be referenced if maski0, otherwise mask will be ignored.
lopts2=true
The final permutation will not be reversed, that is, the Cuthill–McKee ordering will be returned. The bandwidth of the non-reversed matrix will be the same but the profile will be the same or larger (see Wai-Hung and Sherman (1976)).
lopts3=true
The matrix A will be checked for symmetrical sparsity pattern, otherwise not.
lopts4=true
The bandwidth and profile of the unpermuted matrix will be calculated, otherwise not.
lopts5=true
The bandwidth and profile of the permuted matrix will be calculated, otherwise not.
4:     mask: int64int32nag_int array
The dimension of the array mask must be at least n if lopts1=true, and at least 0 otherwise
mask is only referenced if lopts1 is true. A value of maski=0 indicates that the node corresponding to row or column i is not to be referenced. A value of maski0 indicates that the node corresponding to row or column i is to be referenced. In particular, rows and columns not referenced will not be permuted.

Optional Input Parameters

1:     n int64int32nag_int scalar
Default: the first dimension of icolzp-1
n, the order of the matrix A.
Constraint: n1.
2:     nz int64int32nag_int scalar
Default: the dimension of the array irowix.
The number of nonzero elements in the matrix A.
Constraint: nz0.

Output Parameters

1:     permn int64int32nag_int array
This will contain the permutation vector that describes the permutation matrix P for the reordering of the matrix A. The elements of the permutation matrix P are zero except for the unit elements in row i and column permi, i=1,2,n.
2:     info4 int64int32nag_int array
Statistics about the matrix A and the permuted matrix. The quantities below are calculated using any masking in effect otherwise the value zero is returned.
info1
The bandwidth of the matrix A, if lopts4=true.
info2
The profile of the matrix A, if lopts4=true.
info3
The bandwidth of the permuted matrix PAPT, if lopts5=true.
info4
The profile of the permuted matrix PAPT, if lopts5=true.
3:     ifail int64int32nag_int scalar
ifail=0 unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:
   ifail=1
Constraint: n1.
   ifail=2
Constraint: nz1.
   ifail=3
Constraint: 1irowixin for all i.
   ifail=4
Constraint: 1icolzpinz for all i.
   ifail=5
Constraint: icolzp1=1.
Constraint: icolzpn+1=nz+1.
   ifail=6
On entry, the matrix A is not symmetric.
   ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
   ifail=-399
Your licence key may have expired or may not have been installed correctly.
   ifail=-999
Dynamic memory allocation failed.

Accuracy

Not applicable.

Further Comments

The bandwidth for a matrix A=aij is defined as
b = maxij i-j ,   i,j=1,2,,n​ s.t. ​aij0 .  
The profile is defined as
p = j=1 n bj ,  where ​ bj = max i i-j ,   i=1,2,n ​ s.t. ​ aij0 .  

Example

This example reads the CCS representation of a real sparse matrix A and calls nag_sparse_sym_rcm (f11ye) to reorder the rows and columns and displays the results.
function f11ye_example


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

% Reduce the bandwidth of sparse symmetric matrix A

% Define entries of A using Bucky matrix
A = bucky;
[irow,icol,a] = find(A);

n = int64(size(A,1));
nz = int64(size(irow,1));

% Use f11za to get Compressed column storage array icolzp.
irow = int64(irow);
icol = int64(icol);
dup = 'S';
zero = 'K';
[nz, a, icol, irow, icolzp, ifail] = ...
  f11za(...
        n, nz, a, icol, irow, dup, zero);

% Perform bandwidth reduction
use_mask  = false;
do_cm     = false;
check_sym = true;
bw_before = true;
bw_after  = true;
lopts(1:5) = [use_mask,do_cm,check_sym,bw_before,bw_after];
mask       = [int64(0)];

[perm, info, ifail] = f11ye( ...
                             icolzp, irow, lopts, mask);

% Display results
disp('Permutation (perm):');
fprintf(' %4d %4d %4d %4d %4d %4d %4d %4d %4d %4d\n',perm)
fprintf('\nStatistics:\n');
fprintf('  Before:  Bandwidth = %6d\n', info(1));
fprintf('  Before:  Profile   = %6d\n', info(2));
fprintf('  After :  Bandwidth = %6d\n', info(3));
fprintf('  After :  Profile   = %6d\n', info(4));

% Permuted matrix
B = A(perm,perm);

fig1 = figure;
spy(A);
title('Original matrix ordering');
fig2 = figure;
spy(B);
title('Reverse Cuthil-McKee reordering');

f11ye example results

Permutation (perm):
    1    5    2    6    4    3   26    7   30   11
   12   10   21   16   27   25    8   29   17   15
   13    9   22   20   28   24   42   43   18   14
   37   38   23   19   47   48   41   44   32   33
   36   39   52   53   46   49   45   31   34   40
   51   54   50   58   35   57   55   59   56   60

Statistics:
  Before:  Bandwidth =     34
  Before:  Profile   =    490
  After :  Bandwidth =     10
  After :  Profile   =    458
f11ye_fig1.png
f11ye_fig2.png

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