In numerical analysis

Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....

, nested dissection is a divide and conquer

Divide and conquer algorithm

In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...

 heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

 for the solution of sparse

Sparse matrix

In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....

 symmetric systems of linear equations based on graph partitioning. Nested dissection was introduced by ; the name was suggested by Garrett Birkhoff

Garrett Birkhoff

Garrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.The mathematician George Birkhoff was his father....

.

Nested dissection consists of the following steps:

• Form an undirected graph in which the vertices represent rows and columns of the system of linear equations, and an edge represents a nonzero entry in the sparse matrix
  Sparse matrix
  In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
  
   representing the system.
• Recursively
  Recursion
  Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
  
   partition the graph into subgraphs using separators
  Planar separator theorem
  In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices...
  
  , small subsets of vertices the removal of which allows the graph to be partitioned into subgraphs with at most a constant fraction of the number of vertices.
• Perform Cholesky decomposition
  Cholesky decomposition
  In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
  
   (a variant of Gaussian elimination
  Gaussian elimination
  In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
  
   for symmetric matrices), ordering the elimination of the variables by the recursive structure of the partition: each of the two subgraphs formed by removing the separator is eliminated first, and then the separator vertices are eliminated.

As a consequence of this algorithm, the fill-in (the set of nonzero matrix entries created in the Cholesky decomposition that are not part of the input matrix structure) is limited to at most the square of the separator size at each level of the recursive partition. In particular, for planar graphs (frequently arising in the solution of sparse linear systems derived from two-dimensional finite element method

Finite element method

The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...

 meshes) the resulting matrix has O(n log n) nonzeros, due to the planar separator theorem

Planar separator theorem

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices...

 guaranteeing separators of size O(√n). For arbitrary graphs there is a nested dissection that guarantees fill-in within a logarithmic factor of optimal, but this method is not guaranteed to achieve optimal fill-in and finding the optimal dissection is not a solved problem.

See also

• Cycle rank
  Cycle rank
  In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close adigraph is to a directed acyclic graph , in the sense that a DAG has...
  
   of a graph, or a symmetric Boolean matrix, measures the minimum parallel time needed to perform Cholesky decomposition
• Vertex separator
  Vertex separator
  In graph theory, a vertex subset S \subset V is a vertex separator for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components.-Examples:...