4
$\begingroup$

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.

enter image description here

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

enter image description here

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?

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

This does not show you how to implement it, but the context "SparseArray`" contains several useful but undocumented functions.

SeedRandom[1234];
g = RandomGraph[{1000, 6000}];
A = AdjacencyMatrix[g];
p = SparseArray`NestedDissection[A];

MatrixPlot[A[[p, p]]]

enter image description here

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

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.