Math 2.0

Numerical analysis Direct methods for linear systems Theorem

Nested dissection

Builds on Positive definite matrixSparse matrixCholesky decompositionGraphPlanar graphFinite difference method

Statement

Let AA be a real symmetric positive definite sparse matrix whose graph GG has vertex set VV. A separator of GG is a set S⊆VS \subseteq V such that V∖SV \setminus S splits into two parts V1V_1 and V2V_2. No edge of GG joins V1V_1 and V2V_2. The nested dissection ordering is defined recursively. Choose a separator SS; order the vertices of V1V_1 first, then those of V2V_2, and those of SS last. Order V1V_1 and V2V_2 by the same rule, applied to the subgraphs they induce, until the parts are small.

Let AA be the matrix of the five-point finite difference Laplacian on a k×kk \times k grid, so n=k2n = k^2. Let each separator be a grid line that splits the current rectangle into two halves. Then the Cholesky factor of AA in this ordering has O(nlog⁡n)O(n \log n) nonzero entries. The factorization takes O(n3/2)O(n^{3/2}) arithmetic operations.

Remarks

Since the vertices of SS come last, no elimination step inside V1V_1 can create fill linking V1V_1 to V2V_2. So the factor has a block structure with two independent blocks and a dense final block for SS. On the grid the separators have size O(m)O(\sqrt{m}) for a subgrid of mm 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 n3/2n^{3/2} nonzeros and costs about n2n^2 operations. The same bounds hold for any matrix whose graph is planar, by the planar separator theorem of Lipton and Tarjan. On the grid, no ordering beats the operation count O(n3/2)O(n^{3/2}) by more than a constant factor.

Going deeper

For a student

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×k×kk \times k \times k grid becomes O(n2)O(n^2) operations with n=k3n = k^3.

Reading path

To understand this page from the ground up, read these 15 pages in order. The foundations come first.

Show the path as a graph
Finite difference method, concept, no evidence levelFinite difference met…conceptGraph, concept, no evidence levelGraphconceptMatrix, definition, no evidence levelMatrixdefinitionPlanar graph, concept, no evidence levelPlanar graphconceptPositive definite matrix, concept, no evidence levelPositive definite mat…conceptSparse matrix, concept, no evidence levelSparse matrixconceptSquare matrix, definition, no evidence levelSquare matrixdefinitionTranspose, definition, no evidence levelTransposedefinitionLower triangular matrix, definition, no evidence levelLower triangular matr…definitionSymmetric matrix, definition, no evidence levelSymmetric matrixdefinitionConjugate transpose, definition, no evidence levelConjugate transposedefinitionHermitian matrix, definition, no evidence levelHermitian matrixdefinitionPositive definite matrix, definition, no evidence levelPositive definite mat…definitionCholesky decomposition, statement, no evidence levelCholesky decompositionstatementNested dissection, statement, no evidence levelNested dissectionstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Finite difference method concept
  2. Graph concept
  3. Matrix definition
  4. Planar graph concept
  5. Positive definite matrix concept
  6. Sparse matrix concept
  7. Square matrix definition
  8. Transpose definition
  9. Lower triangular matrix definition
  10. Symmetric matrix definition
  11. Conjugate transpose definition
  12. Hermitian matrix definition
  13. Positive definite matrix definition
  14. Cholesky decomposition statement
  15. Nested dissection statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Nested_dissection
About this page
Tag9DTJ87P4R1
URIm2://9DTJ87P4R1
Kindstatement, theorem
WritingW0 stub
MSC65F50, 65F05, 65N22
StatusThis copy of the site has no build data. Run m2 status 9DTJ87P4R1.
AboutSparse matrix, Cholesky decomposition
UsesPositive definite matrix, Sparse matrix, Cholesky decomposition, Graph, Planar graph, Finite difference method
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by