1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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$
    – Bill Greene
    Apr 27, 2015 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, 2015 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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