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