When using 9-point stencil finite difference or finite element method, every vertex has 8 neighbors except ones on the boundary. In the picture in previous blog, every smallest square is a clique in 9-point grid. Regular 9-point grid is what Nested Dissection was invented for originally. 5-point grid and 9-point grid are quite different for fill-reducing. As the benchmark shows, MESHND performs very well except the very small grids for 9-point grid. Though MESHND is so good in this condition, further improvement can be achieved.
For fill-reducing, minimal separators are essential. Original Nested Dissection, which MESHND implemented, uses horizontal or vertical lines as separators and for every subgraph, heuristically the line dividing the subgraph equally is chosen. Considering MESHND is so good for 9-point grid, it is acceptable to restrict the separators to be horizontal or vertical lines. But it is better to choose the line resulting minimum fill-in directly.
In the grid, a rectangle , whose neighbor is , can be separated into two smaller rectangles and by a horizontal or vertical line . Compared with fill-in, nonzeros in the factorization can be calculated more straightforward. The minimum nonzeros of
is the nonzeros of
This method can be extended to more general case. can be any component and is its separator. The object can be changed to operations in the factorization, which is the quadratic sum of nonzeros of all vertices. This is also included in the demo, though commented out. Minimizing operations leads to a different ordering but it will not be discussed here.
The ordering shown in the demo is only one of many cases resulting minimum fill-in. When the grid is very small, AMD is better than MESHND. But the method proposed here surpasses both methods in all cases I have tested(Table 2, Table 3). The improvement over MESHND is very small (only 3-4 percent) for large square grid(Table 2). So in this case where Nested Dissection originate, though dividing the graph equally is not the best choice, it is only little worse than the best choice.
When the grid is not square, the improvement is more significant as the aspect ratio increases(Table 3). It is interesting that relative difference between AMD and MEHSND also becomes larger as the aspect ratio increases(Table 3).
The minimum fill-in of grid is . Regressing the result of this method, the minimum fill-in of grid may be . As pointed out, AMD is a good complement for Nested Dissection, not only when the grid is too small, but also when the grid is too slim. I suppose that the distance is important for fill-reducing, not only the size. A square is a disc for 9-point grid. In Nested Dissection, a disc is split into 4 smaller discs and every smaller disc is further split, which produces very good result. When the shape is different, maybe some other skills can be added to improve the result.
 A. George, Nested dissection of a regular finite-element mesh.
 V. Bouchitté, I. Todinca, Treewidth and minimum fill-in grouping the minimal separators.
 A. George, J. Liu, E. Ng, Computer Solution of Sparse Linear Systems.