Semi-Lower Triangular Matrix

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 (ascend).

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.

Benson

[Matt J]

How sparse is a matrix of a typical size, as measured by nnz(A)/numel(A)?

[Matt J]

and re-order the rows from top to the bottom according to their # of non-zero elements (descend).

Don't you mean "ascend", not "descend"? A lower triangular matrix will often have an ascending number of non-zeros.

[Benson Gou]

Hi, Matt,

Thanks for your replies. Yes, it should be ascend instead of descend.

Normally the sparse is 10% for nnz(A)/numel(A).

Best regards, Benson

[Matt J]

It seems to me that your algorithm fails with the following input

A =

     0     0     0     0
     0     1     0     0
     0     0     1     1
     0     0     1     1

In step 3, the algorithm must eventually reduce A to its sub-matrix A(3:end,3:end)=ones(2) with no way to make that sub-matrix lower triangular.

However, it is clearly possible to make the original A lower triangular just by interchanging columns 1 and 4,

B =

       0     0     0     0
       0     1     0     0
       1     0     1     0
       1     0     1     0

[Stephen23]

Duplicate:

https://www.mathworks.com/matlabcentral/answers/420730-a-challenging-problem-how-to-obtain-a-semi-lower-triangular-matrix-from-a-general-matrix

[Benson Gou]

Hi, Matt,

Thanks for your feedback.

Yes, I forgot to mention that if there are zeros columns in A, I will first move all of those zero columns to the right hand of matrix B.

My algorithm given above only deals with non-zero columns.

Best regards, Benson