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 symrcm works in 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.

How symrcm runs on the GPU

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 memory and 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

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 [].

Related functions to explore

These functions work well alongside symrcm. Each page has runnable examples you can try in the browser.

bandwidth, issymmetric, gpuArray, ishermitian

Open-source implementation

Unlike proprietary runtimes, every RunMat function is open-source. Read exactly how symrcm works, line by line, in Rust.

• View symrcm.rs on GitHub
• Learn how the runtime works
• Found a bug? Open an issue with a minimal reproduction.

About RunMat

RunMat is an open-source runtime that executes MATLAB-syntax code — faster, on any GPU, with no license required.

• Simulations that took hours now take minutes. RunMat automatically optimizes your math for GPU execution on Apple, Nvidia, and AMD hardware. No code changes needed.
• Start running code in seconds. Open the browser sandbox or download a single binary. No license server, no IT ticket, no setup.
• A full development environment. GPU-accelerated 2D and 3D plotting, automatic versioning on every save, and a browser IDE you can share with a link.

Getting started · Benchmarks · Pricing