symrcm — Compute symmetric reverse Cuthill-McKee permutations that reduce matrix bandwidth.
r = symrcm(A) returns a permutation vector for reordering symmetric or structurally symmetric matrices to reduce bandwidth. Use A(r, r) to obtain a tighter band structure, matching MATLAB-compatible ordering behavior.
Syntax
p = symrcm(A)Inputs
| Name | Type | Required | Default | Description |
|---|---|---|---|---|
A | Any | Yes | — | Input matrix. |
Returns
| Name | Type | Description |
|---|---|---|
p | NumericArray | Permutation row vector (1-based indices) from reverse Cuthill-McKee ordering. |
Errors
| Identifier | When | Message |
|---|---|---|
RunMat:symrcm:InvalidInput | Input shape/type cannot be interpreted as a numeric or logical square matrix. | symrcm: invalid input |
RunMat:symrcm:Internal | Runtime fails while constructing intermediate tensors or adjacency structures. | symrcm: internal runtime failure |
How symrcm works
- Treats the input as an undirected graph based on the pattern of
A + A'. Any value that is not exactly zero (includingNaNorInf) 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.
Does RunMat run symrcm 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))Using symrcm with coding agents
Open a RunMat example with live inputs, then ask the agent to explain how symrcm changes the result.
Run a small symrcm example, explain the result, then change one input and compare the output.
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 Linalg functions
Open-source implementation
Unlike proprietary runtimes, every RunMat function is open-source. Read exactly how symrcm is executed, line by line, in Rust.
- View the source for symrcm in Rust on GitHub
- Learn how the RunMat 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 blazing on any GPU. It is licensed under the Apache 2.0 license.
- RunMat automatically optimizes your math for GPU execution on Apple, Nvidia, and AMD hardware. No code changes needed. Simulations that took hours now take minutes.
- Start running code in seconds. RunMat runs in the browser, on the desktop, or from the CLI. No license server, no IT ticket.