123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178 |
- <HTML>
- <!--
- Copyright (c) Lie-Quan Lee and Jeremy Siek, 2001
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Minimum Degree Ordering</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1><A NAME="sec:mmd">
- <img src="figs/python.gif" alt="(Python)"/>
- <TT>minimum_degree_ordering</TT>
- </H1>
- <pre>
- template <class AdjacencyGraph, class OutDegreeMap,
- class InversePermutationMap,
- class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap>
- void minimum_degree_ordering
- (AdjacencyGraph& G,
- OutDegreeMap outdegree,
- InversePermutationMap inverse_perm,
- PermutationMap perm,
- SuperNodeSizeMap supernode_size, int delta, VertexIndexMap id)
- </pre>
- <p>The minimum degree ordering algorithm [<A
- HREF="bibliography.html#LIU:MMD">21</A>, <A
- href="bibliography.html#George:evolution">35</a>] is a fill-in
- reduction matrix reordering algorithm. When solving a system of
- equations such as <i>A x = b</i> using a sparse version of Cholesky
- factorization (which is a variant of Gaussian elimination for
- symmetric matrices), often times elements in the matrix that were once
- zero become non-zero due to the elimination process. This is what is
- referred to as "fill-in", and fill-in is bad because it
- makes the matrix less sparse and therefore consume more time and space
- in later stages of the elimintation and in computations that use the
- resulting factorization. Now it turns out that reordering the rows of
- a matrix can have a dramatic affect on the amount of fill-in that
- occurs. So instead of solving <i>A x = b</i>, we instead solve the
- reordered (but equivalent) system <i>(P A P<sup>T</sup>)(P x) = P
- b</i>. Finding the optimal ordering is an NP-complete problem (e.i.,
- it can not be solved in a reasonable amount of time) so instead we
- just find an ordering that is "good enough" using
- heuristics. The minimum degree ordering algorithm is one such
- approach.
- <p>
- A symmetric matrix <TT>A</TT> is typically represented with an
- undirected graph, however for this function we require the input to be
- a directed graph. Each nonzero matrix entry <TT>A(i, j)</TT> must be
- represented by two directed edges (<TT>e(i,j)</TT> and
- <TT>e(j,i)</TT>) in <TT>G</TT>.
- <p>
- The output of the algorithm are the vertices in the new ordering.
- <pre>
- inverse_perm[new_index[u]] == old_index[u]
- </pre>
- <p> and the permutation from the old index to the new index.
- <pre>
- perm[old_index[u]] == new_index[u]
- </pre>
- <p>The following equations are always held.
- <pre>
- for (size_type i = 0; i != inverse_perm.size(); ++i)
- perm[inverse_perm[i]] == i;
- </pre>
- <h3>Parameters</h3>
- <ul>
- <li> <tt>AdjacencyGraph& G</tt> (IN) <br>
- A directed graph. The graph's type must be a model of <a
- href="./AdjacencyGraph.html">Adjacency Graph</a>,
- <a
- href="./VertexListGraph.html">Vertex List Graph</a>,
- <a href="./IncidenceGraph.html">Incidence Graph</a>,
- and <a href="./MutableGraph.html">Mutable Graph</a>.
- In addition, the functions <tt>num_vertices()</tt> and
- <TT>out_degree()</TT> are required.
- <li> <tt>OutDegreeMap outdegree</tt>  (WORK) <br>
- This is used internally to store the out degree of vertices. This
- must be a <a href="../../property_map/doc/LvaluePropertyMap.html">
- LvaluePropertyMap</a> with key type the same as the vertex
- descriptor type of the graph, and with a value type that is an
- integer type.
- <li> <tt>InversePermutationMap inverse_perm</tt>  (OUT) <br>
- The new vertex ordering, given as the mapping from the
- new indices to the old indices (an inverse permutation).
- This must be an <a href="../../property_map/doc/LvaluePropertyMap.html">
- LvaluePropertyMap</a> with a value type and key type a signed integer.
- <li> <tt>PermutationMap perm</tt>  (OUT) <br>
- The new vertex ordering, given as the mapping from the
- old indices to the new indices (a permutation).
- This must be an <a href="../../property_map/doc/LvaluePropertyMap.html">
- LvaluePropertyMap</a> with a value type and key type a signed integer.
- <li> <tt>SuperNodeSizeMap supernode_size</tt>  (WORK/OUT) <br>
- This is used internally to record the size of supernodes and is also
- useful information to have. This is a <a
- href="../../property_map/doc/LvaluePropertyMap.html">
- LvaluePropertyMap</a> with an unsigned integer value type and key
- type of vertex descriptor.
- <li> <tt>int delta</tt>  (IN) <br>
- Multiple elimination control variable. If it is larger than or equal
- to zero then multiple elimination is enabled. The value of
- <tt>delta</tt> specifies the difference between the minimum degree
- and the degree of vertices that are to be eliminated.
-
- <li> <tt>VertexIndexMap id</tt>  (IN) <br>
- Used internally to map vertices to their indices. This must be a <a
- href="../../property_map/doc/ReadablePropertyMap.html"> Readable
- Property Map</a> with key type the same as the vertex descriptor of
- the graph and a value type that is some unsigned integer type.
- </ul>
- <h3>Example</h3>
- See <a
- href="../example/minimum_degree_ordering.cpp"><tt>example/minimum_degree_ordering.cpp</tt></a>.
- <h3>Implementation Notes</h3>
- <p>UNDER CONSTRUCTION
- <p>It chooses the vertex with minimum degree in the graph at each step of
- simulating Gaussian elimination process.
- <p>This implementation provided a number of enhancements
- including mass elimination, incomplete degree update, multiple
- elimination, and external degree. See [<A
- href="bibliography.html#George:evolution">35</a>] for a historical
- survey of the minimum degree algorithm.
- <p>
- An <b>elimination graph</b> <i>G<sub>v</sub></i> is obtained from the
- graph <i>G</i> by removing vertex <i>v</i> and all of its incident
- edges and by then adding edges to make all of the vertices adjacent to
- <i>v</i> into a clique (that is, add an edge between each pair of
- adjacent vertices if an edge doesn't already exist).
- Suppose that graph <i>G</i> is the graph representing the nonzero
- structure of a matrix <i>A</i>. Then performing a step of Guassian
- elimination on row <i>i</i> of matrix <i>A</i> is equivalent to
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2001</TD><TD>
- <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>) <br>
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|