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

1 次查看（过去 30 天）

显示更早的评论

Benson Gou 2018-9-25

1
链接

此问题的直接链接

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

编辑： Matt J 2018-10-9

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

16 个评论
显示 14更早的评论隐藏 14更早的评论

Benson Gou 2018-9-26

编辑：Benson Gou 2018-9-26

Thanks you all for your responses. I would like to add more descriptions on my question: I want to convert a general sparse matrix (non-zeros elements are integers, and the sum of each row is zero except one row which only has one non-zero 1). Please verify it in matrix A given above. I want to add two requirements on the new matrix B: 1. Just like lower triangular matrix, each row only introduces one new non-zero column comparing with the previous rows. For our case, the difference is that we may have multiple rows introduce the same new non-zero column. For example, B=[1 0 0 0 0 0 1 -1 0 0 0 0 2 -1 -1 0 0 0 -1 0 1 0 0 0 0 0 1 -1 0 0 2 -1 0 -1 0 0 3 -1 0 0 -1 -1 0 0 -1 0 2 -1]; In matrix B, the 3rd and 4th rows introduce the same one non-zero column (column 3), and 5th and 6th rows introduce the same one non-zero column (column 4), and the last two rows introduce two new columns (columns 5 and 6). In another word, we do not want two new columns occur earlier than necessary (each row introduces only one non-zero column as possible as it can). We want to push them (2 new non-zero columns or more new non-zero columns) to the right of B. 2. Besides the above requirement, we hope we could push columns with most non-zero elements to the left of B. This requirement may be related to requirement 1.

If it is still not clear, please feel free to let me know. Thank you all for your great help with this interesting problem.

Benson Gou 2018-10-9

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 2018-10-9

编辑：Matt J 2018-10-9

@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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

OCDER 2018-9-25

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/420730-a-challenging-problem-how-to-obtain-a-semi-lower-triangular-matrix-from-a-general-matrix#answer_338393

在 MATLAB Online 中打开

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 个评论
显示 5更早的评论隐藏 5更早的评论

Benson Gou 2018-9-26

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 2018-9-26

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

请先登录，再进行评论。

请先登录，再回答此问题。

类别

Radar Phased Array System Toolbox Waveform Design and Signal Synthesis Matched Filter and Ambiguity Function

在 Help Center 和 File Exchange 中查找有关 Matched Filter and Ambiguity Function 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by