Nested dissection


In numerical analysis, nested dissection is a divide and conquer heuristic for the solution of sparse symmetric systems of linear equations based on graph partitioning. Nested dissection was introduced by ; the name was suggested by Garrett Birkhoff.
Nested dissection consists of the following steps:
As a consequence of this algorithm, the fill-in is limited to at most the square of the separator size at each level of the recursive partition. In particular, for planar graphs the resulting matrix has O nonzeros, due to the planar separator theorem guaranteeing separators of size O. For arbitrary graphs there is a nested dissection that guarantees fill-in within a factor of optimal, where d is the maximum degree and m is the number of non-zeros.