A challenging problem: how to obtain a semi-lower triangular matrix from a general matrix?
2 次查看(过去 30 天)
显示 更早的评论
Dear All,
I want to convert a general sparse matrix into a semi-lower triangular matrix. For example, a given matrix A:
A=[0 0 1 -1; -1 2 1 0; 0 2 -1 -1; -1 0 0 1;-1 -1 3 -1; 0 0 1 0; 0 0 -1 1;2 0 -1 -1];
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/196601/image.png)
Re-order the rows and columns, A can be converted into B:
B=[1 0 0 0; 1 -1 0 0; -1 1 0 0; 0 1 -1 0; -1 -1 2 0; 1 0 -1 2; -1 -1 0 2; 3 -1 -1 -1];
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/196602/image.png)
My code works well but it is very slow. For a 10000 by 10000 matrix, it takes more than 1 hour. For your information, I would like to share with you my algorithm.
My algorithm:
1. For a given sparse matrix A, we count the # of non-zeros elements in all rows, and re-order the rows from top to the bottom according to their # of non-zero elements (descend).
2. Deal with the first row whose # of non-zero elements is 1 (if a row with # = 1 does not exist, we select a row for its # = 2). If this "1" occurs at column j, switch the column 1 and column j.
3. Define the sub-matrix A(2:end,2:end) as a new A and repeat the above steps until the entire matrix is done.
The above steps will lead us to matrix B.
I do not know if someone could help find a faster algorithm than mine.
So far I got replies from Bruno Luong, OCDER, Matt J, and Stephen Cobeldick. Thank them all for their big help. But this equation is still open for solution. I hope you continue to investigate this challenging and interesting problem. I am looking forward to any better ideas.
Benson
Texas, USA
16 个评论
回答(1 个)
OCDER
2018-9-25
A = [ 0 0 1 -1;
-1 2 1 0;
0 2 -1 -1;
-1 0 0 1;
-1 -1 3 -1;
0 0 1 0];
[~, SortedRowIdx] = sort(sum(A == 0, 2), 'descend');
B = A(SortedRowIdx, :);
[~, SortedColIdx] = sort(sum(B == 0, 1), 'ascend');
B = B(:, SortedColIdx);
B =
1 0 0 0
1 -1 0 0
0 1 -1 0
1 0 -1 2
-1 -1 0 2
3 -1 -1 -1
Is the issue that this is too slow though?
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!