1
$\begingroup$

I've the following Matlab code:

r = symrcm(A(2:end, 2:end)); 
prcm = [1 r + 1]; 
spy(A(prcm, prcm));

where A should be sparse connectivity matrix.

I understood what it does:

  1. Finds a permutation vector r of the submatrix of A A(2:end, 2:end) (produced by the reverse Cuthill-McKee algorithm)

  2. Creates a vector prcm which is basically a vector with a $1$ in the first position and all other elements of r increased by $1$.

  3. This prcm vector applied to A as A(prcm, prcm) logically means that we're going to permutate all rows and columns of A according to the reverse Cuthill-McKee algorithm except the first row and the first column. So the resulting matrix would look something like this:

    enter image description here

    Ignore the specific numbers that you see in the plot.

Question

Why would one want such a permutation of the rows and columns of a matrix?

From what I've been reading and I've observed applying, for example, the guassian elimination to this matrix would produce a disastrous fill-in after trying to remove all entries of the first row (Check chapter 5.7 from "A first course in numerical methods" by Ascher and Greif). So, who wrote this code definitely didn't want to find a permutation of $A$ to apply the guassian elimination...

$\endgroup$
  • $\begingroup$ Well, I have no idea at the moment, but it would be much easier to guess if you told us what the purpose of the full program is, or at least what it does with $A$ after the permutation. $\endgroup$ – Federico Poloni Oct 15 '16 at 11:26
  • $\begingroup$ @FedericoPoloni Actually there's no relevant code afterwards... $\endgroup$ – nbro Oct 15 '16 at 12:34
  • $\begingroup$ So it just computes the matrix and then does nothing with it? Not even solving a linear system?!? Is this an example from a book or lecture notes? $\endgroup$ – Federico Poloni Oct 15 '16 at 13:07
  • $\begingroup$ @FedericoPoloni It does not solve any linear system. But it's used only to plot the nodes in a graph. The plot emphasises expectedly the connections of node $1$. But I was wondering if there's any other reason of doing it... $\endgroup$ – nbro Oct 15 '16 at 13:11
  • $\begingroup$ Looks like the author is performing a visual inspection and for some reason doesn't want to include the first row col and symrcm is compacting the visual inspection area. That's my two cents of razors. $\endgroup$ – percusse Dec 18 '16 at 20:34
1
$\begingroup$

From your comment "The plot emphasises expectedly the connections of node 1", I guess that maybe the idea is showing that node 1 is connected not only to a set of nodes that are "one close to the other", but its interconnections are spread somewhat evenly across the graph.

Reverse Cuthill-McKee in theory reorders the nodes so that clusters are mapped into nearby positions. Or at least some clusters: those which include the starting vertex. Or something morally similar, at least. So the fact that the nonzeros in row 1 are not an almost adjacent set of entries, (say, $\{2,3,\dots,20\}$), but are spread uniformly across the matrix somehow shows that 1 is a 'well-connected node'.

If that is really the answer, then it seems quite an odd way to measure 'well-connectedness'. There is a lot of academic literature on measures of centrality of vertices in a graph, from Pagerank to the Estrada index, and I have never seen RCM used for this purpose.

$\endgroup$
  • $\begingroup$ By the way, I've also a problem related to the degree of centrality of these nodes in graph or matrix A, so I'm aware a little bit about these methods... the specific problem (the 3 lines) I'm mentioning in my questions are a independent problem that I've: what do these lines produce? I mentioned also the plot because these lines appear also in a script which simply plots the matrix A after the permutation. $\endgroup$ – nbro Oct 15 '16 at 13:59
0
$\begingroup$

A very simple hypothesis is that a problem has to be solved in which the "degree of freedom" of node 1 is "constrained". Suppose that the degree of freedom at node $i$ is $u_i$ and that the problem to be solved is $$K\,u=f,$$ where matrix $K$ is symmetric and singular, and we now that $f$ belongs to the range of $K$. A common approach in such cases, if the null space of $K$ has dimension 1, is to impose $u_1 = 0$ and simply solve $$K_{{2\dots N},{2\dots N}} \; u_{2\dots N} = f_{2\dots N}$$

$\endgroup$
  • $\begingroup$ No, I mean $u_1=0$, so that you obtain the solving system simply by deleting first row and column of matrix $K$. This is a common situation say in heat equation with Neumann b.c, where the solution is determined up to an additive constant. $\endgroup$ – Stefano M Nov 15 '16 at 15:15
  • $\begingroup$ Oh, ok, you are right, I was thinking to a different setup (finding $u$ in the kernel of $K$, so the indetermination is on a multiplicative coefficient). $\endgroup$ – Federico Poloni Nov 15 '16 at 15:18

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.