ceph/src/boost/libs/graph/doc/minimum_degree_ordering.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Lie-Quan Lee and Jeremy Siek, 2001
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Boost Graph Library: Minimum Degree Ordering</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1><A NAME="sec:mmd">
  19 <img src="figs/python.gif" alt="(Python)"/>
  20 <TT>minimum_degree_ordering</TT>
  21 </H1>
  22
  23
  24 <pre>
  25   template &lt;class AdjacencyGraph, class OutDegreeMap,
  26            class InversePermutationMap,
  27            class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap&gt;
  28   void minimum_degree_ordering
  29     (AdjacencyGraph& G,
  30      OutDegreeMap outdegree,
  31      InversePermutationMap inverse_perm,
  32      PermutationMap perm,
  33      SuperNodeSizeMap supernode_size, int delta, VertexIndexMap id)
  34 </pre>
  35
  36 <p>The minimum degree ordering algorithm&nbsp;[<A
  37 HREF="bibliography.html#LIU:MMD">21</A>, <A
  38 href="bibliography.html#George:evolution">35</a>] is a fill-in
  39 reduction matrix reordering algorithm.  When solving a system of
  40 equations such as <i>A x = b</i> using a sparse version of Cholesky
  41 factorization (which is a variant of Gaussian elimination for
  42 symmetric matrices), often times elements in the matrix that were once
  43 zero become non-zero due to the elimination process. This is what is
  44 referred to as &quot;fill-in&quot;, and fill-in is bad because it
  45 makes the matrix less sparse and therefore consume more time and space
  46 in later stages of the elimintation and in computations that use the
  47 resulting factorization. Now it turns out that reordering the rows of
  48 a matrix can have a dramatic affect on the amount of fill-in that
  49 occurs. So instead of solving <i>A x = b</i>, we instead solve the
  50 reordered (but equivalent) system <i>(P A P<sup>T</sup>)(P x) = P
  51 b</i>. Finding the optimal ordering is an NP-complete problem (e.i.,
  52 it can not be solved in a reasonable amount of time) so instead we
  53 just find an ordering that is &quot;good enough&quot; using
  54 heuristics. The minimum degree ordering algorithm is one such
  55 approach.
  56
  57 <p>
  58 A symmetric matrix <TT>A</TT> is typically represented with an
  59 undirected graph, however for this function we require the input to be
  60 a directed graph.  Each nonzero matrix entry <TT>A(i, j)</TT> must be
  61 represented by two directed edges (<TT>e(i,j)</TT> and
  62 <TT>e(j,i)</TT>) in <TT>G</TT>.
  63
  64 <p>
  65 The output of the algorithm are the vertices in the new ordering.
  66 <pre>
  67   inverse_perm[new_index[u]] == old_index[u]
  68 </pre>
  69 <p> and the permutation from the old index to the new index.
  70 <pre>
  71   perm[old_index[u]] == new_index[u]
  72 </pre>
  73 <p>The following equations are always held.
  74 <pre>
  75   for (size_type i = 0; i != inverse_perm.size(); ++i)
  76     perm[inverse_perm[i]] == i;
  77 </pre>
  78
  79 <h3>Parameters</h3>
  80
  81 <ul>
  82
  83 <li> <tt>AdjacencyGraph&amp; G</tt> &nbsp;(IN) <br>
  84   A directed graph. The graph's type must be a model of <a
  85   href="./AdjacencyGraph.html">Adjacency Graph</a>,
  86   <a
  87   href="./VertexListGraph.html">Vertex List Graph</a>,
  88   <a href="./IncidenceGraph.html">Incidence Graph</a>,
  89   and <a href="./MutableGraph.html">Mutable Graph</a>.
  90   In addition, the functions <tt>num_vertices()</tt> and
  91   <TT>out_degree()</TT> are required.
  92
  93 <li> <tt>OutDegreeMap outdegree</tt> &nbsp(WORK) <br>
  94   This is used internally to store the out degree of vertices.  This
  95   must be a <a href="../../property_map/doc/LvaluePropertyMap.html">
  96   LvaluePropertyMap</a> with key type the same as the vertex
  97   descriptor type of the graph, and with a value type that is an
  98   integer type.
  99
 100 <li> <tt>InversePermutationMap inverse_perm</tt> &nbsp(OUT) <br>
 101   The new vertex ordering, given as the mapping from the
 102   new indices to the old indices (an inverse permutation).
 103   This must be an <a href="../../property_map/doc/LvaluePropertyMap.html">
 104   LvaluePropertyMap</a> with a value type and key type a signed integer.
 105
 106 <li> <tt>PermutationMap perm</tt> &nbsp(OUT) <br>
 107   The new vertex ordering, given as the mapping from the
 108   old indices to the new indices (a permutation).
 109   This must be an <a href="../../property_map/doc/LvaluePropertyMap.html">
 110   LvaluePropertyMap</a> with a value type and key type a signed integer.
 111
 112 <li> <tt>SuperNodeSizeMap supernode_size</tt> &nbsp(WORK/OUT) <br>
 113   This is used internally to record the size of supernodes and is also
 114   useful information to have. This is a <a
 115   href="../../property_map/doc/LvaluePropertyMap.html">
 116   LvaluePropertyMap</a> with an unsigned integer value type and key
 117   type of vertex descriptor.
 118
 119 <li> <tt>int delta</tt> &nbsp(IN) <br>
 120   Multiple elimination control variable. If it is larger than or equal
 121   to zero then multiple elimination is enabled. The value of
 122   <tt>delta</tt> specifies the difference between the minimum degree
 123   and the degree of vertices that are to be eliminated.
 124
 125 <li> <tt>VertexIndexMap id</tt> &nbsp(IN) <br>
 126   Used internally to map vertices to their indices. This must be a <a
 127   href="../../property_map/doc/ReadablePropertyMap.html"> Readable
 128   Property Map</a> with key type the same as the vertex descriptor of
 129   the graph and a value type that is some unsigned integer type.
 130
 131 </ul>
 132
 133
 134 <h3>Example</h3>
 135
 136 See <a
 137 href="../example/minimum_degree_ordering.cpp"><tt>example/minimum_degree_ordering.cpp</tt></a>.
 138
 139
 140 <h3>Implementation Notes</h3>
 141
 142 <p>UNDER CONSTRUCTION
 143
 144 <p>It chooses the vertex with minimum degree in the graph at each step of
 145 simulating Gaussian elimination process.
 146
 147 <p>This implementation provided a number of enhancements
 148 including mass elimination, incomplete degree update, multiple
 149 elimination, and external degree. See&nbsp;[<A
 150 href="bibliography.html#George:evolution">35</a>] for a historical
 151 survey of the minimum degree algorithm.
 152
 153 <p>
 154 An <b>elimination graph</b> <i>G<sub>v</sub></i> is obtained from the
 155 graph <i>G</i> by removing vertex <i>v</i> and all of its incident
 156 edges and by then adding edges to make all of the vertices adjacent to
 157 <i>v</i> into a clique (that is, add an edge between each pair of
 158 adjacent vertices if an edge doesn't already exist).
 159
 160 Suppose that graph <i>G</i> is the graph representing the nonzero
 161 structure of a matrix <i>A</i>. Then performing a step of Guassian
 162 elimination on row <i>i</i> of matrix <i>A</i> is equivalent to
 163
 164
 165
 166
 167
 168 <br>
 169 <HR>
 170 <TABLE>
 171 <TR valign=top>
 172 <TD nowrap>Copyright &copy; 2001</TD><TD>
 173 <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>
 174 <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>)
 175 </TD></TR></TABLE>
 176
 177 </BODY>
 178 </HTML>