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

1 view (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
Benson Gou on 9 Oct 2018
Dear OCDER and Bruno,
I run your code on the matrix A given as below: 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];
But your codes generated the following results:
It is close but still a little problem: 4th row and 7th row are not correct.
Thanks a lot for your efforts.
Bei
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 Bruno,
Thanks for your great help. Your code is very fast. But there is one thing I want to point out: like lower triangular matrix, each row introduces a new non-zero column, I hope each new row only introduces a new non-zero column comparing with previous rows. Please see the new description of my problem.
Thanks a lot again. Benson.
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