RunMat
GitHub

View all functions

CategoryMath: Linalg & Structure
GPUYes
BLAS/LAPACK

symrcm — Compute the symmetric reverse Cuthill-McKee permutation that reduces matrix bandwidth.

r = symrcm(A) returns a permutation vector that reorders a symmetric (or structurally symmetric) matrix to reduce its bandwidth. You can use the permutation as A(r, r) to obtain a matrix with a tighter band structure, which improves factorisation and linear solve performance for sparse matrices.

How does the symrcm function behave in MATLAB / RunMat?

  • Treats the input as an undirected graph based on the pattern of A + A'. Any value that is not exactly zero (including NaN or Inf) creates an edge; diagonal entries are ignored because they do not affect bandwidth.
  • Accepts numeric, logical, and complex matrices. Logical and integer inputs are promoted to double precision internally, and complex entries are considered nonzero when either the real or imaginary component is nonzero.
  • Requires a square matrix (scalars and the empty matrix are allowed). Inputs with more than two non-singleton dimensions raise an error, matching MATLAB matrix semantics.
  • Processes disconnected components independently. Each component starts from a minimum degree vertex, runs a Cuthill-McKee breadth-first search, and the component ordering is reversed to produce the symmetric variant.
  • Returns a row vector of 1-based indices. Fully diagonal or zero matrices produce the identity permutation.

GPU behavior

RunMat first asks the active acceleration provider whether it implements the sym_rcm hook. The WGPU backend exposes this hook today and downloads the matrix once to reuse the optimised CPU algorithm before returning the permutation. Providers without support (or those that report an error) trigger an automatic gather and reuse the host implementation, so results stay correct regardless of GPU capabilities.

GPU residency

No. The runtime gathers GPU matrices automatically when computing the permutation today. When native GPU implementations land, the same builtin will run entirely on the device without code changes. You can still call gpuArray explicitly to mirror MATLAB workflows, but it is optional in RunMat.

Examples of using symrcm in MATLAB / RunMat

Reducing bandwidth of a near-band matrix

A = [4 1 0 0 2;
     1 4 1 0 0;
     0 1 4 1 0;
     0 0 1 4 1;
     2 0 0 1 4];
r = symrcm(A);
B = A(r, r);
bandwidth(A)
bandwidth(B)

Handling disconnected components with symrcm

A = [1 1 0 0 0;
     1 1 0 0 0;
     0 0 1 0 1;
     0 0 0 1 1;
     0 0 1 1 1];
r = symrcm(A);
B = A(r, r)

Using symrcm with logical adjacency matrices

adj = logical([0 1 0 0;
               1 0 1 0;
               0 1 0 1;
               0 0 1 0]);
r = symrcm(adj)

Applying symrcm to GPU matrices

G = gpuArray([0 1 0 0 2;
              1 0 1 0 0;
              0 1 0 1 0;
              0 0 1 0 1;
              2 0 0 1 0]);
r = symrcm(G);
H = gather(G(r, r))

FAQ

What class of matrices benefit from symrcm?

Any symmetric (or structurally symmetric) sparse matrix whose bandwidth dominates solver cost, such as discretised PDE operators, circuit matrices, or graph Laplacians.

Does symrcm modify the matrix?

No. It returns a permutation vector. Apply it as A(r, r) or reorder vectors with x(r).

What happens if the matrix is not symmetric?

RunMat mirrors MATLAB and forms the pattern of A + A' internally. As long as the matrix has symmetric nonzero structure, symrcm works. Strongly asymmetric inputs may lead to less effective orderings but still produce a valid permutation.

Are diagonal entries considered?

Diagonal entries are ignored when building the graph. Only off-diagonal nonzeros contribute edges, which aligns with MATLAB semantics.

How are NaNs or Infs handled?

Any value that is not numerically equal to zero is treated as nonzero, including NaN or Inf. This matches MATLAB's structural interpretation.

Can I use symrcm on dense matrices?

Yes. Dense inputs are supported. For dense matrices, the result is typically the identity permutation because all vertices have high degree.

How do I verify the permutation improves bandwidth?

Compute bandwidth(A) and bandwidth(A(r, r)) and compare the results. Lower lower/upper bandwidth values indicate a tighter band and more efficient factorizations.

What output shape should I expect?

The permutation is returned as a row vector (1 × n). The empty matrix returns the empty row vector [].

See also

rcm, symamd, bandwidth, issymmetric, gpuArray

Source & Feedback