# NAG FL Interfacef11yef (sym_​rcm)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

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

## 2Specification

Fortran Interface
 Subroutine f11yef ( n, nnz, mask, perm, info,
 Integer, Intent (In) :: n, nnz, icolzp(n+1), irowix(nnz), mask(*) Integer, Intent (Inout) :: ifail Integer, Intent (Out) :: perm(n), info(4) Logical, Intent (In) :: lopts(5)
#include <nag.h>
 void f11yef_ (const Integer *n, const Integer *nnz, const Integer icolzp[], const Integer irowix[], const logical lopts[], const Integer mask[], Integer perm[], Integer info[], Integer *ifail)
The routine may be called by the names f11yef or nagf_sparse_sym_rcm.

## 3Description

f11yef takes the compressed column storage (CCS) representation (see Section 2.1.3 in the F11 Chapter Introduction) of an $n×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 Section 9).
f11yef can be useful for solving systems of equations $Ax=b$, as the permuted system $PA{P}^{\mathrm{T}}\left(Px\right)=Pb$ (where $P$ is the permutation matrix described by the vector perm returned by f11yef) may require less storage space and/or less computational steps when solving (see Wai-Hung and Sherman (1976)).
f11yef may be used prior to f11jaf and f11jbf (see Section 10 in f11jbf).
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

## 5Arguments

1: $\mathbf{n}$Integer Input
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 1$.
2: $\mathbf{nnz}$Integer Input
On entry: the number of nonzero elements in the matrix $A$.
Constraint: ${\mathbf{nnz}}\ge 0$.
3: $\mathbf{icolzp}\left({\mathbf{n}}+1\right)$Integer array Input
On entry: icolzp records the index into irowix which starts each new column.
Constraints:
• $1\le {\mathbf{icolzp}}\left(\mathit{i}\right)\le {\mathbf{nnz}}+1$, for $\mathit{i}=2,3,\dots ,{\mathbf{n}}$;
• ${\mathbf{icolzp}}\left(1\right)=1$;
• ${\mathbf{icolzp}}\left({\mathbf{n}}+1\right)={\mathbf{nnz}}+1$, where ${\mathbf{icolzp}}\left(i\right)$ holds the position integer for the starts of the columns in irowix.
4: $\mathbf{irowix}\left({\mathbf{nnz}}\right)$Integer array Input
On entry: the row indices corresponding to the nonzero elements in the matrix $A$.
Constraint: $1\le {\mathbf{irowix}}\left(\mathit{i}\right)\le {\mathbf{n}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{nnz}}$.
5: $\mathbf{lopts}\left(5\right)$Logical array Input
On entry: the options to be used by f11yef.
${\mathbf{lopts}}\left(1\right)=\mathrm{.TRUE.}$
Row/column $i$ of the matrix $A$ will only be referenced if ${\mathbf{mask}}\left(i\right)\ne 0$, otherwise ${\mathbf{mask}}$ will be ignored.
${\mathbf{lopts}}\left(2\right)=\mathrm{.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)).
${\mathbf{lopts}}\left(3\right)=\mathrm{.TRUE.}$
The matrix $A$ will be checked for symmetrical sparsity pattern, otherwise not.
${\mathbf{lopts}}\left(4\right)=\mathrm{.TRUE.}$
The bandwidth and profile of the unpermuted matrix will be calculated, otherwise not.
${\mathbf{lopts}}\left(5\right)=\mathrm{.TRUE.}$
The bandwidth and profile of the permuted matrix will be calculated, otherwise not.
6: $\mathbf{mask}\left(*\right)$Integer array Input
Note: the dimension of the array mask must be at least ${\mathbf{n}}$ if ${\mathbf{lopts}}\left(1\right)=\mathrm{.TRUE.}$, and at least $0$ otherwise.
On entry: mask is only referenced if ${\mathbf{lopts}}\left(1\right)$ is .TRUE.. A value of ${\mathbf{mask}}\left(i\right)=0$ indicates that the node corresponding to row or column $i$ is not to be referenced. A value of ${\mathbf{mask}}\left(i\right)\ne 0$ 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.
7: $\mathbf{perm}\left({\mathbf{n}}\right)$Integer array Output
On exit: 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 ${\mathbf{perm}}\left(i\right)$, $i=1,2,\dots n$.
8: $\mathbf{info}\left(4\right)$Integer array Output
On exit: 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.
${\mathbf{info}}\left(1\right)$
The bandwidth of the matrix $A$, if ${\mathbf{lopts}}\left(4\right)=\mathrm{.TRUE.}$.
${\mathbf{info}}\left(2\right)$
The profile of the matrix $A$, if ${\mathbf{lopts}}\left(4\right)=\mathrm{.TRUE.}$.
${\mathbf{info}}\left(3\right)$
The bandwidth of the permuted matrix $PA{P}^{\mathrm{T}}$, if ${\mathbf{lopts}}\left(5\right)=\mathrm{.TRUE.}$.
${\mathbf{info}}\left(4\right)$
The profile of the permuted matrix $PA{P}^{\mathrm{T}}$, if ${\mathbf{lopts}}\left(5\right)=\mathrm{.TRUE.}$.
9: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ or $\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 1$.
${\mathbf{ifail}}=2$
On entry, ${\mathbf{nnz}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{nnz}}\ge 1$.
${\mathbf{ifail}}=3$
On entry, ${\mathbf{irowix}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{irowix}}\left(i\right)\le {\mathbf{n}}$ for all $i$.
${\mathbf{ifail}}=4$
On entry, ${\mathbf{icolzp}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{nnz}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{icolzp}}\left(i\right)\le {\mathbf{nnz}}$ for all $i$.
${\mathbf{ifail}}=5$
On entry, ${\mathbf{icolzp}}\left(1\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{icolzp}}\left(1\right)=1$.
On entry, ${\mathbf{icolzp}}\left({\mathbf{n}}+1\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{nnz}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{icolzp}}\left({\mathbf{n}}+1\right)={\mathbf{nnz}}+1$.
${\mathbf{ifail}}=6$
On entry, the matrix $A$ is not symmetric.
Element $\left(⟨\mathit{\text{value}}⟩,⟨\mathit{\text{value}}⟩\right)$ has no symmetric element.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

Not applicable.

## 8Parallelism and Performance

f11yef is not threaded in any implementation.

The bandwidth for a matrix $A=\left({a}_{ij}\right)$ is defined as
 $b = maxij |i-j| , i,j=1,2,…,n​ s.t. ​aij≠0 .$
The profile is defined as
 $p = ∑ j=1 n bj , where ​ bj = max i |i-j| , i=1,2,…n ​ s.t. ​ aij≠0 .$

## 10Example

This example reads the CCS representation of a real sparse matrix $A$ and calls f11yef to reorder the rows and columns and displays the results.

### 10.1Program Text

Program Text (f11yefe.f90)

### 10.2Program Data

Program Data (f11yefe.d)

### 10.3Program Results

Program Results (f11yefe.r)