Sparse matrix re-ordering

2020 3 11
3 个回答
回答已采纳
更新时间：2020 3 25
5 次查看（30 天）

0 个投票

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

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

James Tursa
James Tursa 2020-3-11
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?

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

the cyclist
the cyclist 2020-3-13

0 个投票

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.

4 个评论
显示 2更早的评论 隐藏 2更早的评论

Romeo Tahal
Romeo Tahal 2020-3-13
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
Romeo Tahal 2020-3-24
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
the cyclist 2020-3-24
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
Romeo Tahal 2020-3-25
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.

请先登录，再进行评论。

更多回答（2 个）

the cyclist
the cyclist 2020-3-11

0 个投票

[sorted_nodes,index_to_sorting_order] = sort(nodes)

2 个评论
显示 无 隐藏 无

Romeo Tahal
Romeo Tahal 2020-3-12
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
the cyclist 2020-3-12
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.

请先登录，再进行评论。

Romeo Tahal
Romeo Tahal 2020-3-12

0 个投票

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

2 个评论
显示 无 隐藏 无

the cyclist
the cyclist 2020-3-12
编辑：the cyclist 2020-3-12
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
Romeo Tahal 2020-3-12
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

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by