When I run the following (in Matlab) on a sparse matrix $A$, I get larger band width. The symrcm (symmetric reverse Cuthill-McKee permutation) is not guarenteed to find the smallest band width, but it makes no sense for it to increase. What is wrong here?

reorderingForSmallBand = symrcm(A);
A = A(reorderingForSmallBand,reorderingForSmallBand);

Running spy(A) on $A$ before and after reordering yields: Before (PDF) and After (PDF)

Originally, my matrix $A$ has this form (PDF). I also wonder if it is a big deal to have large bandwidth as the backslash solver in Matlab says it is above the limit for a solver exploiting the banded structure. Is it any advantage for an iterative solver to have small band width?


Nothing is wrong here. The Cuthill-McKee algorithm is a greedy algorithm, and doesn't depend too much on the order of A on input. The reverse Cuthill-McKee algorithm is often used to produce nice orders for skyline solvers, and the skyline of the reordered matrix looks indeed quite reasonable. (The bandwidths of Cuthill-McKee and reverse Cuthill-McKee is the same, if I remember correctly.) But I don't know whether Matlab has a special skyline solver. It certainly has banded solvers, because LAPACK has banded solvers. LAPACK didn't have skyline solvers in the past, so it is quite likely that Matlab has neither. Matlat however has general sparse direct solvers, but the reverse Cuthill-McKee ordering is not too useful for those.

  • 3
    $\begingroup$ CM and RCM are really obsolete for state of the art sparse solvers like those in MATLAB. In MATLAB it is usually more efficient to simply let the sparse solver (e.g. the backslash operator) apply it's default permutation algorithm (e.g. minimum degree). $\endgroup$ Apr 27 '15 at 19:54
  • $\begingroup$ Are there any function in Matlab which reduces the bandwidth of the original matrix $A$ to the first matrix? $\endgroup$
    – user253249
    Apr 28 '15 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.