Minimum degree algorithm

Minimum degree algorithm

In numerical analysis the minimum degree algorithm is an algorithm used to permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition, to reduce the number of non-zeros in the Cholesky factor. This results in reduced storage requirements and means that the Cholesky factor, or sometimes an incomplete Cholesky factor used as a preconditioner (for example in the preconditioned conjugate gradient algorithm) can be applied with fewer arithmetic operations.

Minimum degree algorithms are often used in the finite element method where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.

Given a linear system

 \mathbf{A}\mathbf{x} = \mathbf{b}

where A is an n \times n real symmetric sparse square matrix the Cholesky factor L will typically suffer 'fill in', that is have more non-zeros than the upper triangle of A. We seek a permutation matrix P , so that the matrix \mathbf{P}^T\mathbf{A}\mathbf{P}, which is also symmetric, has the least possible fill in its Cholesky factor. We solve the reordered system

 \left(\mathbf{P}^T\mathbf{A}\mathbf{P}\right) \left(\mathbf{P}^T\mathbf{x}\right) = \mathbf{P}^T\mathbf{b}.

The problem of finding the best ordering is an NP-complete problem and is thus intractable, so heuristic methods are used instead. The minimum degree algorithm is derived from a method first proposed by Markowitz in 1959 for non-symmetric linear programming problems, which is loosely described as follows. At each step in Gaussian elimination row and column permutations are performed so as to minimize the number of off diagonal non-zeros in the pivot row and column. A symmetric version of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with n vertices, with vertices i and j connected by an edge when a_{ij} \ne 0, and the degree is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.

A version of the minimum degree algorithm was implemented in the MATLAB function symmmd, but has now been superseded by a symmetric approximate multiple minimum degree function symamd, which is faster.

References

  • Markowitz, H. M. (1957). "The elimination form of the inverse and its application to linear programming". Management Science 3 (3): 255–269. JSTOR 2627454. 
  • George, Alan; Liu, Joseph (1989). "The evolution of the Minimum Degree Ordering Algorithm". SIAM Review 31 (1): 1–19. JSTOR 2030845. 
  • Tinney, W. F.; Walker, J. W. (1967). "Direct solution of sparse network equations by optimally ordered triangular factorization". Proc. IEEE 55 (11): 1801–1809. doi:10.1109/PROC.1967.6011. 
  • Rose, D. J. (1972). "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations". In Read, R. C.. Graph Theory and Computing. New York: Academic Press. pp. 183–217. ISBN 0125838506. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Degree-constrained spanning tree — In graph theory, a degree constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree constrained spanning tree problem is to determine whether a particular graph has such a spanning …   Wikipedia

  • Degree (graph theory) — A graph with vertices labeled by degree In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.[1] The degree of a vertex …   Wikipedia

  • Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia

  • Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list …   Wikipedia

  • Christofides algorithm — The goal of the Christofides heuristic algorithm (named after Nicos Christofides) is to find a solution to the instances of the traveling salesman problem where the edge weights satisfy the triangle inequality. Let G = (V,w) be an instance of TSP …   Wikipedia

  • Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… …   Wikipedia

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • 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… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”