# A challenging problem: how to obtain a semi-lower triangular matrix from a general matrix?

7 views (last 30 days)
Benson Gou on 25 Sep 2018
Edited: Matt J on 9 Oct 2018
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];
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];
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
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.

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?
Benson Gou on 26 Sep 2018
Dear OCDER,
Thanks lot for your great help. I run your code but did not get a right matrix B. Would you please check your code again?
Thanks a lot again. Benson