清空筛选条件
清空筛选条件

Sparse matrix re-ordering

6 次查看（过去 30 天）
Romeo Tahal
Romeo Tahal 2020-3-11
评论： Romeo Tahal 2020-3-25
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 个评论
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
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更早的评论
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
[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
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by