Reordering and Nested Dissection
Permuting the unknowns of a sparse matrix before factorization to minimize fill-in and expose parallelism.
Ordering decides the cost
The order in which unknowns are eliminated during a sparse factorization controls how much fill-in occurs, and fill dominates both memory and work. Two orderings of the same matrix can differ by orders of magnitude in factorization cost. Choosing a good ordering is therefore the single most important preprocessing step for a sparse direct solver.
Nested dissection
Nested dissection is a divide-and-conquer ordering. It finds a small set of vertices (a separator) whose removal splits the matrix graph into two roughly equal, disconnected pieces. The separator is numbered last, and each piece is ordered recursively by the same rule. Because the two pieces share no edges except through the separator, eliminating them first creates no fill between them; fill is confined to the small separators. For regular meshes this gives near-optimal fill and factorization cost, and it is provably efficient for graphs with good separators, which includes most PDE meshes.
Other orderings
- Minimum degree: repeatedly eliminate the node with the fewest connections, a greedy local heuristic (AMD is the modern variant)
- Reverse Cuthill-McKee: reduces the matrix bandwidth, helpful for band solvers
- Nested dissection: best asymptotic fill and best parallelism for large 3D problems
Parallelism as a bonus
Nested dissection produces an elimination tree in which independent subtrees can be factorized concurrently, since they touch disjoint sets of unknowns. This makes it the ordering of choice not only for minimizing fill but also for parallel sparse factorization. Graph-partitioning libraries such as METIS compute these separators, and they are used both here and to distribute domains across processors in domain decomposition.
The takeaway
Reordering is invisible in the final answer but decisive in whether a sparse solve is feasible at all. For the large linear systems arising in three-dimensional field and equilibrium solves, nested dissection is what keeps direct factorization within reach on realistic hardware.