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

   1 \documentclass[11pt]{report}
   2
   3 \input{defs}
   4
   5
   6 \setlength\overfullrule{5pt}
   7 \tolerance=10000
   8 \sloppy
   9 \hfuzz=10pt
  10
  11 \makeindex
  12
  13 \begin{document}
  14
  15 \title{An Implementation of the Multiple Minimum Degree Algorithm}
  16 \author{Jeremy G. Siek and Lie Quan Lee}
  17
  18 \maketitle
  19
  20 \section{Introduction}
  21
  22 The minimum degree ordering algorithm \cite{LIU:MMD,George:evolution}
  23 reorders a matrix to reduce fill-in. Fill-in is the term used to refer
  24 to the zero elements of a matrix that become non-zero during the
  25 gaussian elimination process.  Fill-in is bad because it makes the
  26 matrix less sparse and therefore consume more time and space in later
  27 stages of the elimintation and in computations that use the resulting
  28 factorization. Reordering the rows of a matrix can have a dramatic
  29 affect on the amount of fill-in that occurs. So instead of solving
  30 \begin{eqnarray}
  31 A x = b
  32 \end{eqnarray}
  33 we instead solve the reordered (but equivalent) system
  34 \begin{eqnarray}
  35 (P A P^T)(P x) = P b.
  36 \end{eqnarray}
  37 where $P$ is a permutation matrix.
  38
  39 Finding the optimal ordering is an NP-complete problem (e.i., it can
  40 not be solved in a reasonable amount of time) so instead we just find
  41 an ordering that is ``good enough'' using heuristics. The minimum
  42 degree ordering algorithm is one such approach.
  43
  44 A symmetric matrix $A$ is typically represented with an undirected
  45 graph, however for this function we require the input to be a directed
  46 graph.  Each nonzero matrix entry $A_{ij}$ must be represented by two
  47 directed edges, $(i,j)$ and $(j,i)$, in $G$.
  48
  49 An \keyword{elimination graph} $G_v$ is formed by removing vertex $v$
  50 and all of its incident edges from graph $G$ and then adding edges to
  51 make the vertices adjacent to $v$ into a clique\footnote{A clique is a
  52 complete subgraph. That is, it is a subgraph where each vertex is
  53 adjacent to every other vertex in the subgraph}.
  54
  55
  56 quotient graph
  57 set of cliques in the graph
  58
  59
  60 Mass elmination: if $y$ is selected as the minimum degree node then
  61 the the vertices adjacent to $y$ with degree equal to $degree(y) - 1$
  62 can be selected next (in any order).
  63
  64 Two nodes are \keyword{indistinguishable} if they have identical
  65 neighborhood sets. That is,
  66 \begin{eqnarray}
  67 Adj[u] \cup \{ u \} = Adj[v] \bigcup \{ v \}
  68 \end{eqnarray}
  69 Nodes that are indistiguishable can be eliminated at the same time.
  70
  71 A representative for a set of indistiguishable nodes is called a
  72 \keyword{supernode}.
  73
  74 incomplete degree update
  75 external degree
  76
  77
  78
  79
  80 \section{Algorithm Overview}
  81
  82 @d MMD Algorithm Overview @{
  83   @<Eliminate isolated nodes@>
  84
  85 @}
  86
  87
  88
  89
  90 @d Set up a mapping from integers to vertices @{
  91 size_type vid = 0;
  92 typename graph_traits<Graph>::vertex_iterator v, vend;
  93 for (tie(v, vend) = vertices(G); v != vend; ++v, ++vid)
  94   index_vertex_vec[vid] = *v;
  95 index_vertex_map = IndexVertexMap(&index_vertex_vec[0]);
  96 @}
  97
  98
  99 @d Insert vertices into bucket sorter (bucket number equals degree) @{
 100 for (tie(v, vend) = vertices(G); v != vend; ++v) {
 101   put(degree, *v, out_degree(*v, G));
 102   degreelists.push(*v);
 103 }
 104 @}
 105
 106
 107 @d Eliminate isolated nodes (nodes with zero degree) @{
 108 typename DegreeLists::stack list_isolated = degreelists[0];
 109 while (!list_isolated.empty()) {
 110   vertex_t node = list_isolated.top();
 111   marker.mark_done(node);
 112   numbering(node);
 113   numbering.increment();
 114   list_isolated.pop();
 115 }
 116 @}
 117
 118
 119 @d Find first non-empty degree bucket
 120 @{
 121 size_type min_degree = 1;
 122 typename DegreeLists::stack list_min_degree = degreelists[min_degree];
 123 while (list_min_degree.empty()) {
 124   ++min_degree;
 125   list_min_degree = degreelists[min_degree];
 126 }
 127 @}
 128
 129
 130
 131 @d Main Loop
 132 @{
 133 while (!numbering.all_done()) {
 134   eliminated_nodes = work_space.make_stack();
 135   if (delta >= 0)
 136     while (true) {
 137       @<Find next non-empty degree bucket@>
 138       @<Select a node of minimum degree for elimination@>
 139       eliminate(node);
 140     }
 141   if (numbering.all_done())
 142     break;
 143   update(eliminated_nodes, min_degree);
 144 }
 145 @}
 146
 147
 148 @d Elimination Function
 149 @{
 150 void eliminate(vertex_t node)
 151 {
 152   remove out-edges from the node if the target vertex was
 153     tagged or if it is numbered
 154   add vertices adjacent to node to the clique
 155   put all numbered adjacent vertices into the temporary neighbors stack
 156
 157   @<Perform element absorption optimization@>
 158 }
 159 @}
 160
 161
 162 @d
 163 @{
 164 bool remove_out_edges_predicate::operator()(edge_t e)
 165 {
 166   vertex_t v = target(e, *g);
 167   bool is_tagged = marker->is_tagged(dist);
 168   bool is_numbered = numbering.is_numbered(v);
 169   if (is_numbered)
 170     neighbors->push(id[v]);
 171   if (!is_tagged)
 172     marker->mark_tagged(v);
 173   return is_tagged || is_numbered;
 174 }
 175 @}
 176
 177
 178
 179 How does this work????
 180
 181 Does \code{is\_tagged} mean in the clique??
 182
 183 @d Perform element absorption optimization
 184 @{
 185 while (!neighbors.empty()) {
 186   size_type n_id = neighbors.top();
 187   vertex_t neighbor = index_vertex_map[n_id];
 188   adjacency_iterator i, i_end;
 189   for (tie(i, i_end) = adjacent_vertices(neighbor, G); i != i_end; ++i) {
 190     vertex_t i_node = *i;
 191     if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
 192       marker.mark_tagged(i_node);
 193       add_edge(node, i_node, G);
 194     }
 195   }
 196   neighbors.pop();
 197 }
 198 @}
 199
 200
 201
 202 @d
 203 @{
 204 predicateRemoveEdge1<Graph, MarkerP, NumberingD,
 205                      typename Workspace::stack, VertexIndexMap>
 206   p(G, marker, numbering, element_neighbor, vertex_index_map);
 207
 208 remove_out_edge_if(node, p, G);
 209 @}
 210
 211
 212 \section{The Interface}
 213
 214
 215 @d Interface of the MMD function @{
 216 template<class Graph, class DegreeMap,
 217          class InversePermutationMap,
 218          class PermutationMap,
 219          class SuperNodeMap, class VertexIndexMap>
 220 void minimum_degree_ordering
 221   (Graph& G,
 222    DegreeMap degree,
 223    InversePermutationMap inverse_perm,
 224    PermutationMap perm,
 225    SuperNodeMap supernode_size,
 226    int delta,
 227    VertexIndexMap vertex_index_map)
 228 @}
 229
 230
 231
 232 \section{Representing Disjoint Stacks}
 233
 234 Given a set of $N$ integers (where the integer values range from zero
 235 to $N-1$), we want to keep track of a collection of stacks of
 236 integers. It so happens that an integer will appear in at most one
 237 stack at a time, so the stacks form disjoint sets.  Because of these
 238 restrictions, we can use one big array to store all the stacks,
 239 intertwined with one another.  No allocation/deallocation happens in
 240 the \code{push()}/\code{pop()} methods so this is faster than using
 241 \code{std::stack}.
 242
 243
 244 \section{Bucket Sorting}
 245
 246
 247
 248 @d Bucket Sorter Class Interface @{
 249 template <typename BucketMap, typename ValueIndexMap>
 250 class bucket_sorter {
 251 public:
 252   typedef typename property_traits<BucketMap>::value_type bucket_type;
 253   typedef typename property_traits<ValueIndex>::key_type value_type;
 254   typedef typename property_traits<ValueIndex>::value_type size_type;
 255
 256   bucket_sorter(size_type length, bucket_type max_bucket,
 257                 const BucketMap& bucket = BucketMap(),
 258                 const ValueIndexMap& index_map = ValueIndexMap());
 259   void remove(const value_type& x);
 260   void push(const value_type& x);
 261   void update(const value_type& x);
 262
 263   class stack {
 264   public:
 265     void push(const value_type& x);
 266     void pop();
 267     value_type& top();
 268     const value_type& top() const;
 269     bool empty() const;
 270   private:
 271     @<Bucket Stack Constructor@>
 272     @<Bucket Stack Data Members@>
 273   };
 274   stack operator[](const bucket_type& i);
 275 private:
 276   @<Bucket Sorter Data Members@>
 277 };
 278 @}
 279
 280 \code{BucketMap} is a \concept{LvaluePropertyMap} that converts a
 281 value object to a bucket number (an integer). The range of the mapping
 282 must be finite. \code{ValueIndexMap} is a \concept{LvaluePropertyMap}
 283 that maps from value objects to a unique integer. At the top of the
 284 definition of \code{bucket\_sorter} we create some typedefs for the
 285 bucket number type, the value type, and the index type.
 286
 287 @d Bucket Sorter Data Members @{
 288 std::vector<size_type>   head;
 289 std::vector<size_type>   next;
 290 std::vector<size_type>   prev;
 291 std::vector<value_type>  id_to_value;
 292 BucketMap bucket_map;
 293 ValueIndexMap index_map;
 294 @}
 295
 296
 297 \code{N} is the maximum integer that the \code{index\_map} will map a
 298 value object to (the minimum is assumed to be zero).
 299
 300 @d Bucket Sorter Constructor @{
 301 bucket_sorter::bucket_sorter
 302   (size_type N, bucket_type max_bucket,
 303    const BucketMap& bucket_map = BucketMap(),
 304    const ValueIndexMap& index_map = ValueIndexMap())
 305   : head(max_bucket, invalid_value()),
 306     next(N, invalid_value()),
 307     prev(N, invalid_value()),
 308     id_to_value(N),
 309     bucket_map(bucket_map), index_map(index_map) { }
 310 @}
 311
 312
 313
 314
 315 \bibliographystyle{abbrv}
 316 \bibliography{jtran,ggcl,optimization,generic-programming,cad}
 317
 318 \end{document}