Matrix reordering to block diagonal form

Question

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.

Answer 1

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