A challenging problem: how to obtain a semi-lower triangular matrix from a general matrix?
2 views (last 30 days)
Show older comments
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 Comments
Matt J
on 9 Oct 2018
Edited: Matt J
on 9 Oct 2018
@Benson,
Are you sure the thing you are ultimately trying to accomplish would not work just as well if you could triangularize T1*A*T2 for some pre-/post transformations T1, T2? You still haven't told us what you plan to do with the triangularized result.
Answers (1)
OCDER
on 25 Sep 2018
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?
7 Comments
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!