---
tag: 9DTJ87P4R1
kind: statement
role: theorem
name: Nested dissection
msc: [65F50, 65F05, 65N22]
uses: [0KX66CZMBB, JGACZYEEY7, 0WKG8CYY6A, 00C0BR7D7H, 0NC9R64TXP, X7HYEBA5SA]
about: [JGACZYEEY7, 0WKG8CYY6A]
sources:
  - url: https://en.wikipedia.org/wiki/Nested_dissection
same_as:
  wikidata: Q6997812
  wikipedia: Nested dissection
---

## Statement

Let $A$ be a real symmetric [[positive definite|0KX66CZMBB]] [[sparse matrix|JGACZYEEY7]] whose [[graph|00C0BR7D7H]] $G$ has vertex set $V$.
A *separator* of $G$ is a set $S \subseteq V$ such that $V \setminus S$ splits into two parts $V_1$ and $V_2$.
No edge of $G$ joins $V_1$ and $V_2$.
The *nested dissection ordering* is defined recursively.
Choose a separator $S$; order the vertices of $V_1$ first, then those of $V_2$, and those of $S$ last.
Order $V_1$ and $V_2$ by the same rule, applied to the subgraphs they induce, until the parts are small.

Let $A$ be the matrix of the five-point [[finite difference|X7HYEBA5SA]] Laplacian on a $k \times k$ grid, so $n = k^2$.
Let each separator be a grid line that splits the current rectangle into two halves.
Then the [[Cholesky factor|0WKG8CYY6A]] of $A$ in this ordering has $O(n \log n)$ nonzero entries.
The factorization takes $O(n^{3/2})$ arithmetic operations.

## Remarks

Since the vertices of $S$ come last, no elimination step inside $V_1$ can create fill linking $V_1$ to $V_2$.
So the factor has a block structure with two independent blocks and a dense final block for $S$.
On the grid the separators have size $O(\sqrt{m})$ for a subgrid of $m$ points, and summing the dense separator blocks over the levels of the recursion gives the two bounds.
For comparison, a banded ordering of the same grid gives a factor with about $n^{3/2}$ nonzeros and costs about $n^2$ operations.
The same bounds hold for any matrix whose graph is [[planar|0NC9R64TXP]], by the planar separator theorem of Lipton and Tarjan.
On the grid, no ordering beats the operation count $O(n^{3/2})$ by more than a constant factor.

## Explanations

### L1 human

Cut the problem into two halves with a thin wall, solve the two halves separately, and handle the wall last.
Then cut each half the same way, and so on.
Because the two halves never talk to each other directly, elimination cannot spread nonzeros from one half to the other.
This divide-and-conquer order makes direct solvers for two-dimensional grids much cheaper.

### L2 human

Nested dissection is the main fill-reducing ordering for matrices from discretized partial differential equations.
Its recursive structure also exposes parallelism: the independent halves can be factored at the same time.
In three dimensions the separators are larger, and the cost on a $k \times k \times k$ grid becomes $O(n^2)$ operations with $n = k^3$.