# Nested dissection on regular grid

When solving sparse linear systems using direct factorization methods, the ordering strategy used significantly impacts the fill-in factor of non-zero elements in the factors. One such ordering strategy is nested dissection. I am wondering if it is possible to come up with the nested dissection ordering ahead of time given only the grid parameters (assume an M x N square finite difference grid with first order differences).

Edit I just found that there is code that does this: http://www.cise.ufl.edu/research/sparse/meshnd/

Suppose you have an $n_x \times n_y$ grid, and that it is acceptable to have leaf nodes with 100 vertices. One can then define a recursive function where the arguments are:
The routine then simply has to compute the product of the local dimensions to decide whether or not the domain is an acceptably small to be a leaf, and then, if so, write the leaf node natural indices (say $\mathrm{natural}(x,y)=x+y n_x$ for an $n_x \times n_y$ grid), otherwise, cut the largest subdomain dimension, recurse on the left and right pieces, and then write the separator natural indices.