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)


    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example


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.


[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)


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)).


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


Compulsory Input Parameters

1:     icolzpn+1 int64int32nag_int array
icolzp records the index into irowix which starts each new column.
  • 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).
Row/column i of the matrix A will only be referenced if maski0, otherwise mask will be ignored.
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)).
The matrix A will be checked for symmetrical sparsity pattern, otherwise not.
The bandwidth and profile of the unpermuted matrix will be calculated, otherwise not.
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.
The bandwidth of the matrix A, if lopts4=true.
The profile of the matrix A, if lopts4=true.
The bandwidth of the permuted matrix PAPT, if lopts5=true.
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:
Constraint: n1.
Constraint: nz1.
Constraint: 1irowixin for all i.
Constraint: 1icolzpinz for all i.
Constraint: icolzp1=1.
Constraint: icolzpn+1=nz+1.
On entry, the matrix A is not symmetric.
An unexpected error has been triggered by this routine. Please contact NAG.
Your licence key may have expired or may not have been installed correctly.
Dynamic memory allocation failed.


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 .  


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] = ...
        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('  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;
title('Original matrix ordering');
fig2 = figure;
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

  Before:  Bandwidth =     34
  Before:  Profile   =    490
  After :  Bandwidth =     10
  After :  Profile   =    458

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