Nested dissection#

Nested dissection (ND) is a recursive, divide-and-conquer fill-reducing reordering. A balanced vertex separator of the matrix’s adjacency graph is chosen, the two disconnected sub-graphs are ordered (recursively, by the same procedure), and the separator vertices are placed last. The recursion bottoms out on small sub-graphs, where a local heuristic — typically AMD — finishes the ordering.

The separator-last property bounds the fill-in to the union of fills inside each sub-graph plus a contribution from the separator. For meshes with a regular structure this gives asymptotically optimal complexity: for the 2-D 5-point stencil on an \(n\)-row grid the factorisation has \(O(n^{3/2})\) nonzeros and costs \(O(n^2)\) work to compute — beating AMD’s worst case by a polynomial factor.

When to use nested dissection#

Large mesh-based matrices from finite-element, finite-difference, or finite-volume discretisations, where the underlying geometry produces good separators.
Parallel sparse direct factorisation — the dissection tree exposes independent sub-problems that can be factorised concurrently, which AMD’s flat ordering cannot.
For moderate-sized matrices without obvious geometric structure, AMD often wins on both runtime and final fill — ND’s setup cost is dominated by the partitioner.

Using nested dissection#

auto reorder_factory =
    gko::experimental::reorder::NestedDissection<double, int>::build().on(exec);
auto perm = reorder_factory->generate(system_matrix);
auto permuted = system_matrix->permute(perm.get());

To combine ND with an MC64 matching/scaling step and a downstream direct solver in one shot, see ScaledReordered.

Implementation notes#

The partitioning is delegated to METIS; the quality of the resulting ordering is dominated by METIS’s separator quality. Ginkgo’s NestedDissection is therefore only available when Ginkgo is built with -DGINKGO_BUILD_METIS=ON. Trying to instantiate it without METIS available raises a build-time error.

Note

The recursive base case uses an internal AMD-like local ordering rather than calling AMD directly. If you need a different bottom-level strategy, you have to modify METIS itself.