naginterfaces.library.sparse.sym_​rcm

naginterfaces.library.sparse.sym_rcm(icolzp, irowix, lopts, mask=None)

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

For full information please refer to the NAG Library document for f11ye

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/f11/f11yef.html

Parameters

icolzpint, array-like, shape $(n+1)$

$icolzp$ records the index into $irowix$ which starts each new column.

irowixint, array-like, shape $\left(\text{nnz}\right)$

The row indices corresponding to the nonzero elements in the matrix $A$.

loptsbool, array-like, shape $\left(5\right)$

The options to be used by sym_rcm.

$lopts\left[0\right]=True$

Row/column $i$ of the matrix $A$ will only be referenced if $mask[i-1]\ne 0$, otherwise $mask$ will be ignored.

$lopts\left[1\right]=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)).

$lopts\left[2\right]=True$

The matrix $A$ will be checked for symmetrical sparsity pattern, otherwise not.

$lopts\left[3\right]=True$

The bandwidth and profile of the unpermuted matrix will be calculated, otherwise not.

$lopts\left[4\right]=True$

The bandwidth and profile of the permuted matrix will be calculated, otherwise not.

maskNone or int, array-like, shape $(:)$, optional

Note: the required length for this argument is determined as follows: if $lopts\left[0\right]=True$: $n$; otherwise: $0$.

$mask$ is only referenced if $lopts\left[0\right]$ is $True$. A value of $mask[i-1]=0$ indicates that the node corresponding to row or column $i$ is not to be referenced. A value of $mask[i-1]\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.

Returns

permint, ndarray, shape $(:)$

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 $perm[i-1]$, $i=1,2,\dots n$.

infoint, ndarray, shape $\left(4\right)$

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.

$info\left[0\right]$

The bandwidth of the matrix $A$, if $lopts\left[3\right]=True$.

$info\left[1\right]$

The profile of the matrix $A$, if $lopts\left[3\right]=True$.

$info\left[2\right]$

The bandwidth of the permuted matrix $PA{P}^T$, if $lopts\left[4\right]=True$.

$info\left[3\right]$

The profile of the permuted matrix $PA{P}^T$, if $lopts\left[4\right]=True$.

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $2$)

On entry, $\text{nnz}=⟨value⟩$.

Constraint: $\text{nnz}\ge 1$.

(errno $3$)

On entry, $irowix[⟨value⟩]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le irowix[i-1]\le n$ for all $i$.

(errno $4$)

On entry, $icolzp[⟨value⟩]=⟨value⟩$ and $\text{nnz}=⟨value⟩$.

Constraint: $1\le icolzp[i-1]\le \text{nnz}$ for all $i$.

(errno $5$)

On entry, $icolzp\left[0\right]=⟨value⟩$.

Constraint: $icolzp\left[0\right]=1$.

(errno $5$)

On entry, $icolzp\left[n\right]=⟨value⟩$ and $\text{nnz}=⟨value⟩$.

Constraint: $icolzp\left[n\right]=\text{nnz}+1$.

(errno $6$)

On entry, the matrix $A$ is not symmetric.

Element $(⟨value⟩,⟨value⟩)$ has no symmetric element.

Notes

sym_rcm takes the compressed column storage (CCS) representation (see the F11 Introduction) of an $n\times 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).

sym_rcm can be useful for solving systems of equations $Ax=b$, as the permuted system $PA{P}^T\left(Px\right)=Pb$ (where $P$ is the permutation matrix described by the vector $perm$ returned by sym_rcm) may require less storage space and/or less computational steps when solving (see Wai-Hung and Sherman (1976)).

sym_rcm may be used prior to real_symm_precon_ichol() and real_symm_precon_ichol_solve().

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