Sparse matrix re-ordering

Hello everyone,

I have a question I'd like to ask.

When you have a (sparse) matrix, you can plot the graph and find the degree of nodes. When some re-ordering is applied, the sequence of the nodes changes form the lowest degree to the highest degree.

Example: suppose I have a 10 node system with the following degrees: 3-3-5-3-5-2-6-3-1-3. (Node:1-2-3-4-5-6-7-8-9-10)

Now I apply a re-ordering based on the degrees, and my node sequence now becomes: 9-6-1-2-4-8-10-3-5-7.

How do I find the updated matrix from this new sequence? Is there a specific MATLAB function, or do I need to write some code?

Any help is really appreciated.

Romeo

[James Tursa]

Maybe I am not understanding the question, but why can't you just use the sort( ) function? Can you give a complete example using MATLAB variables of inputs and desired outputs?

Answer 1

[the cyclist]

I tried to generalize your code as follows.

A = [-1 -2  0 4  0  0  0  1  0 0;
      3  2  0 0  0  0 -4  0  0 3;
      0  0  5 7 -6  0  3  4  0 1;
      2  0  1 1 -1  0  0  0  0 0;
      0  0  2 4 -1  8  6  0  0 3;
      0  0  0 0  2 -2  4  0  0 0;
      0  3 -3 0  1  9  5 -3 -6 0;
     -1  0  2 0  0  0  4 -5  0 0;
      0  0  0 0  0  0 -1  0  2 0;
      0  2  2 0  5  0  0  0  0 7];

% Store the graph info for the original array, in the first element of a
% new cell array
G{1} = graph(A,'upper');

N = length(A);

% Initialize the output as an empty vector that we will append to
output = nan(N,1);

original = 1:N;

for i = 1:N
    % Find the degree list (and store for later inspection)
    deg{i}     = degree(simplify(G{i}));
    % Sort the degree list
    [deg{i},k] = sort(deg{i},'ascend');
    % Remove lowest degree from graph, and store new graph
    G{i+1}     = rmnode(G{i},k(1));
    % Add lowest degree position to output
    output(i)  = original(k(1));
    % Delete the lowest degree position from the original list
    original(k(1)) = [];
end

However, I don't get the same final output as you state. (The first few match with yours.)

I can't determine whose is incorrect. I tried to comment my code very carefully, so that you could follow what I did, and find a coding mistake.

[Romeo Tahal]

Hello Mr. Cyclist,

The required output is from a textbook. Only the end result is given. I believe that the ordering scheme from the textbook must be correct. I was experiencing the same issue when doing the ordering 'by hand'. The code you provided has given me some insight how to deal with the loop. I will try to 'troubleshoot' the outcome of your code, and when I find what's wrong I will definitely give you an update.

Regards,

Romeo

[Romeo Tahal]

Hi Mr. Cyclist,

I may have an update for you and I also have a request. Like you mentioned, the ordering matches for the first three nodes, that is 9-6-1. After that it doesn't match anymore.

Before deleting node 1, node 1 was connected to node 2, node 4 and node 8. Now that node 1 is removed, three additional vertices are created: from 2 to 4, from 2 to 8, and from 4 to 8. After updating the links, node 10 becomes the one with the minimum degrees. Therefore 10 follows after 1. The same reasoning applies for the others when deleted.

Is it possible that you can help me to modify the code you provided, so I can come up with the correct ordering?

Thanks in advance.

Romeo

[the cyclist]

I actually did nothing other than modify your code to

1. use cell arrays elements such as deg{1} instead of dynamically named variables such as deg_1.
2. take advantage of those cell arrays, so that the loop could be written in a general way

To be frank, I never really tried to understand your actual algorithm, and I don't know much about graphs. I can take a look, but I don't know how much help I'll be.

[Romeo Tahal]

This is very tough, I know. That's the reason I'm looking for expert advise since I'm a newbie to matlab. If I had to do this by hand, I would need maybe a couple of hours. However, putting everything in code is a real challenge. I already spent almost a week on this.

Answer 2

[the cyclist]

[sorted_nodes,index_to_sorting_order] = sort(nodes)

[Romeo Tahal]

Thanks Mr. Cyclist,

Based on your reply I found the relevant function in MATLAB. The challenge is now, what if I have to delete the nodes with the minimal degrees one at a time until I come up with the final ordering. For my example, node 9 has the minimum degree, so I delete that one and update the sequence. If I do it by hand, I can see that the next node with the minimum degree is node 6. Now I delete node 6, update the order, and so on. Doing this by hand is obvious, but to put this into a loop is challenging. I would really appreciate some tips or functions I can use to accomplish this. And, by the way, the nodes should keep their original numbers. MATLAB renumbers the nodes after deleting one.

Kind regards,

Romeo

[the cyclist]

It seems to me that you have all the information you need, from the original sorting and associated index. But, maybe I am misunderstanding. So, let's take a simple example, where we can do everything you want "by hand". Suppose your original node list is

nodes = [3 3 4 2];

Then my solution gives you the following information:

[sorted_nodes,index_to_sorting_order] = sort(nodes)

sorted_nodes =

     2     3     3     4


index_to_sorting_order =

     4     1     2     3

Can you tell us what exactly you expect for the output? (Please use MATLAB syntax to define it, if possible, and not just a description in words.) Don't worry about the algorithm to get there. Just what does the output needs to be.

Answer 3

[Romeo Tahal]

OK.

Let me give an example what I was trying to do by manual calculation.

A = [-1 -2 0 4 0 0 0 1 0 0;3 2 0 0 0 0 -4 0 0 3;0 0 5 7 -6 0 3 4 0 1;2 0 1 1 -1 0 0 0 0 0;0 0 2 4 -1 8 6 0 0 3;0 0 0 0 2 -2 4 0 0 0;

0 3 -3 0 1 9 5 -3 -6 0;-1 0 2 0 0 0 4 -5 0 0;0 0 0 0 0 0 -1 0 2 0;0 2 2 0 5 0 0 0 0 7];

G1 = graph(A,'upper');

deg = degree(simplify(G1));

P = colperm(A);

Nodemin = P(:,min(P));

Gupd = rmnode(G1,Nodemin);

deg1 = degree(simplify(Gupd));

[deg1,k] = sort(deg1,'ascend');

Gupd1 = rmnode(Gupd,6);

deg2 = degree(simplify(Gupd1));

[deg2,k] = sort(deg2,'ascend');

Gupd2 = rmnode(Gupd1,1);

......

In the end I should get for the re-ordering of the nodes: 9-6-1-10-4-2-3-5-7-8

Putting all of this in a loop is where I'm stuck at. Can you help me with this?

Regards,

Romeo

[the cyclist]

Of all of those variables you generated, which ones did you really need as output? (As opposed to variables that you just happened to generate because you needed them for later calculation.)

For example, do you only need that the input is the matrix A, and the output is

output = [9 6 1 10 4 2 3 5 7 8]

?

Or do you need the entire sequence of deg1, deg2, etc, and Gupd, Gupd1, etc?

This is exactly why I asked for you to tell us what is the output you need, and not the algorithm. (But it is handy to see how you got there, I suppose.)

[Romeo Tahal]

What I need is the output = [9 6 1 10 4 2 3 5 7 8]

Based on this output, I will reorder matrix A so that I can do a LU decomposition.

Regards,

Romeo