MlevelNestedDissection() fails to produce a dissection for a specific graph

Hi,

Some back ground information first. I've been using Metis v4 heavily for almost ten years now and this is the first time I see this problem. In my application, I use METIS_NodeND() function with default control parameters to find optimal reordering for symmetric sparse matrices. Size of the matrix can vary from 1000 to 100M unknowns. The matrix I am having problems with is of average size of 600K unknowns and can be solved on a 32-bit system.

When I call Metis for this matrix, it gets into an infinite loop inside MlevelNestedDissection() function and runs out of stack memory. I tracked the problem down to SplitGraphOrder() function that under certain inputs does not split the graph at all, that's is lgraph = graph and rgraph = 0. Since the graph size at this point is 300 vertices, MMD is not triggered and function gets into an infinite loop. I've tried to investigate what was so special about this small graph and here are some stacks: # of vertices = 251, total graph weight = 693. However, I discovered that one of the vertices in the graph has the weight of 381, and the rest have 1 or 2 weight. I think that's what causing the problem. I think the graph partitioning is based of the assumption that graph can be split into 2 sub-graph of equal weight, which is not true in this case, since one vertex has 381 weight. That's the reason why the graph cannot be split and the function gets into an infinite loop.

You might ask how I ended up with this graph in the first place. Here is my guess. My matrix (600K unknowns) is FEM based with an average of 72 elements per row. However, I also couple it together with SPICE matrix into one big matrix. SPICE block has a small number of unknowns (1000 or so), but each unknown has ~900 entries per row. This creates big unbalance between FEM part and SPICE part and that's what I think results in one node having too much weight. I might be wrong though.

Right now I fixed the problem by forcing Metis to switch to MMD when this occurs. However, if you have a more elegant solution, let me know.

Thanks,
Sergey