# Reorder matrix for nested dissection

I'm implementing a nested dissection linear solver outside of Mathematica and my original data is actually a graph, from which I have to construct an appropriate adjacency matrix to feed into the solver. I want to construct this matrix in the appropriate format using Mathematica. I haven't found any built-in function to do so, but there's probably some way to do it using other graph and linear algebra functions I might not be aware of.

Even if you're not familiar with the nested dissection method, I can explain what I'm trying to do. I start with a graph where the nodes have arbirary numeric labels like this. The adjacency matrix can look like a dense matrix with no particular sparsity pattern.

But the trick of nested dissection reordering is to realize that there are actually 2 independent clusters, connected by another middle cluster. In this case, the independent clusters (using the old labels) are nodes 1, 2, 6 (cluster 1), and nodes 3, 5, 7 (cluster 2). And they are connected by nodes 4, 8, 9 (cluster 3).

So if you reorder the labels, you can get the following graph, which has an adjacency matrix with a better sparsity pattern. In particular, you will have 2 big blocks of zeros. In this case, the blocks that connect nodes 4, 5, 6 with nodes 1, 2, 3 (using the new labels).

It doesn't end there though, because even inside clusters 1 and 2, you can have another nested clustering so you end up with a similar sparsity pattern inside those blocks up to some arbitrary depth that could be specified by the user. I manually renamed the labels for this example. I have big graphs that I can import into Mathematica. What's the best way to do this reordering in Mathematica?

• You might also be interested in FindGraphPartition... – Henrik Schumacher Jun 14 '18 at 23:04

This does not show you how to implement it, but the context "SparseArray" contains several useful but undocumented functions.
SeedRandom[1234];

For g = GridGraph[{100, 100}];, I obtain