Matrix reordering to block diagonal form

5
votes

Give a sparse matrix, how to reorder the rows and columns such that it is in block diagonal like form via row and column permutation?

Row and column permutation are not necessarily coupled like reverse Cuthill-McKee ordering: http://www.mathworks.com/help/matlab/ref/symrcm.html?refresh=true In short, you can independently perform any row or column permutation.

The overall goal is to cluster all the non zero elements towards diagonal line.

2
algorithmmatlabmatrixlinear-algebragraph-algorithm
Technically, any matrix is in block-diagonal form, even if it's just one block. What do you precisely want? Can you give an example, and/or a clarification towards the underlying problem and the reason you want to do block-permutations? – tvo
@tvo It seems clear that the goal is the largest possible number of independent blocks. – btilly
@btilly my comment was made before Dennis edited it by adding the goal. Plus, it's always better to ask then to assume... – tvo
The vertices should be ordered according to topological sorting order, shouldn't they? – beaker

2 Answers

4
votes

Here is one approach.

First make a graph whose vertices are rows and columns. Every non-zero value is a edge between that row and that column.

You can then use a standard graph theory algorithm to detect the connected components of this graph. The single element ones represent all zero rows and columns. Number the others. Those components may have unequal numbers of rows and columns. You can distribute some zero rows and columns to them to make them square.

Your square components will be your blocks, and from the numbering of those components you know what order to put them in. Now just reorder rows and columns to achieve this structure and, voila! (The remaining zero rows/columns will result in a bunch of 0 blocks at the bottom right of the diagonal.)

0
votes

Just an idea, but if you make a new matrix Ab from the original block-matrix A that contains the block-sparsity structure of A. E.g.:

A = [B 0 0; 0 0 C; 0 D 0]; % with matrices 0 (zero elements), B,C and D

Ab = [1 0 0; 0 0 2; 0 3 0]; % with identifiers 1, 2 and 3 (1-->B, 2-->C, 3-->D)

Then Ab is a simple sparse matrix (size 3x3 in the example). You can then use the reverse Cuthill-McKee ordering to get the permutations you want, and apply these permutations to Ab.

p = symrcm(Ab);
Abperm = Ab(p,p);

Then use the identifiers to create the ordered block matrix Aperm from Abperm and you'll have the desired result, I believe.

You'll need to be clever in assigning the identifiers to the individual blocks and so on, but this should be possible.