graph/doc/minimum_degree_ordering.w

\documentclass[11pt]{report}

\input{defs}


\setlength\overfullrule{5pt}
\tolerance=10000
\sloppy
\hfuzz=10pt

\makeindex

\begin{document}

\title{An Implementation of the Multiple Minimum Degree Algorithm}
\author{Jeremy G. Siek and Lie Quan Lee}

\maketitle

\section{Introduction}

The minimum degree ordering algorithm \cite{LIU:MMD,George:evolution}
reorders a matrix to reduce fill-in. Fill-in is the term used to refer
to the zero elements of a matrix that become non-zero during the
gaussian elimination process.  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. Reordering the rows of a matrix can have a dramatic
affect on the amount of fill-in that occurs. So instead of solving
\begin{eqnarray}
A x = b
\end{eqnarray}
we instead solve the reordered (but equivalent) system
\begin{eqnarray}
(P A P^T)(P x) = P b.
\end{eqnarray}
where $P$ is a permutation matrix.

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.

A symmetric matrix $A$ is typically represented with an undirected
graph, however for this function we require the input to be a directed
graph.  Each nonzero matrix entry $A_{ij}$ must be represented by two
directed edges, $(i,j)$ and $(j,i)$, in $G$.

An \keyword{elimination graph} $G_v$ is formed by removing vertex $v$
and all of its incident edges from graph $G$ and then adding edges to
make the vertices adjacent to $v$ into a clique\footnote{A clique is a
complete subgraph. That is, it is a subgraph where each vertex is
adjacent to every other vertex in the subgraph}.


quotient graph
set of cliques in the graph


Mass elmination: if $y$ is selected as the minimum degree node then
the the vertices adjacent to $y$ with degree equal to $degree(y) - 1$
can be selected next (in any order).

Two nodes are \keyword{indistinguishable} if they have identical
neighborhood sets. That is,
\begin{eqnarray}
Adj[u] \cup \{ u \} = Adj[v] \bigcup \{ v \}
\end{eqnarray}
Nodes that are indistiguishable can be eliminated at the same time.

A representative for a set of indistiguishable nodes is called a
\keyword{supernode}.

incomplete degree update
external degree


\section{Algorithm Overview}

@d MMD Algorithm Overview @{
  @<Eliminate isolated nodes@>

@}


@d Set up a mapping from integers to vertices @{
size_type vid = 0;
typename graph_traits<Graph>::vertex_iterator v, vend;
for (tie(v, vend) = vertices(G); v != vend; ++v, ++vid)
  index_vertex_vec[vid] = *v;
index_vertex_map = IndexVertexMap(&index_vertex_vec[0]);
@}


@d Insert vertices into bucket sorter (bucket number equals degree) @{
for (tie(v, vend) = vertices(G); v != vend; ++v) {
  put(degree, *v, out_degree(*v, G));
  degreelists.push(*v);
}
@}


@d Eliminate isolated nodes (nodes with zero degree) @{
typename DegreeLists::stack list_isolated = degreelists[0];
while (!list_isolated.empty()) {
  vertex_t node = list_isolated.top();
  marker.mark_done(node);
  numbering(node);
  numbering.increment();
  list_isolated.pop();
}
@}


@d Find first non-empty degree bucket
@{
size_type min_degree = 1;
typename DegreeLists::stack list_min_degree = degreelists[min_degree];
while (list_min_degree.empty()) {
  ++min_degree;
  list_min_degree = degreelists[min_degree];
}
@}


@d Main Loop
@{
while (!numbering.all_done()) {
  eliminated_nodes = work_space.make_stack();
  if (delta >= 0)
    while (true) {
      @<Find next non-empty degree bucket@>
      @<Select a node of minimum degree for elimination@>
      eliminate(node);
    }
  if (numbering.all_done())
    break;
  update(eliminated_nodes, min_degree);
}
@}


@d Elimination Function
@{
void eliminate(vertex_t node)
{
  remove out-edges from the node if the target vertex was
    tagged or if it is numbered
  add vertices adjacent to node to the clique
  put all numbered adjacent vertices into the temporary neighbors stack

  @<Perform element absorption optimization@>
}
@}


@d
@{
bool remove_out_edges_predicate::operator()(edge_t e)
{
  vertex_t v = target(e, *g);
  bool is_tagged = marker->is_tagged(dist);
  bool is_numbered = numbering.is_numbered(v);
  if (is_numbered)
    neighbors->push(id[v]);
  if (!is_tagged)
    marker->mark_tagged(v);
  return is_tagged || is_numbered;
}
@}


How does this work????

Does \code{is\_tagged} mean in the clique??

@d Perform element absorption optimization
@{
while (!neighbors.empty()) {
  size_type n_id = neighbors.top();
  vertex_t neighbor = index_vertex_map[n_id];
  adjacency_iterator i, i_end;
  for (tie(i, i_end) = adjacent_vertices(neighbor, G); i != i_end; ++i) {
    vertex_t i_node = *i;
    if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
      marker.mark_tagged(i_node);
      add_edge(node, i_node, G);
    }
  }
  neighbors.pop();
}
@}


@d
@{
predicateRemoveEdge1<Graph, MarkerP, NumberingD,
                     typename Workspace::stack, VertexIndexMap>
  p(G, marker, numbering, element_neighbor, vertex_index_map);

remove_out_edge_if(node, p, G);
@}


\section{The Interface}


@d Interface of the MMD function @{
template<class Graph, class DegreeMap,
         class InversePermutationMap,
         class PermutationMap,
         class SuperNodeMap, class VertexIndexMap>
void minimum_degree_ordering
  (Graph& G,
   DegreeMap degree,
   InversePermutationMap inverse_perm,
   PermutationMap perm,
   SuperNodeMap supernode_size,
   int delta,
   VertexIndexMap vertex_index_map)
@}


\section{Representing Disjoint Stacks}

Given a set of $N$ integers (where the integer values range from zero
to $N-1$), we want to keep track of a collection of stacks of
integers. It so happens that an integer will appear in at most one
stack at a time, so the stacks form disjoint sets.  Because of these
restrictions, we can use one big array to store all the stacks,
intertwined with one another.  No allocation/deallocation happens in
the \code{push()}/\code{pop()} methods so this is faster than using
\code{std::stack}.


\section{Bucket Sorting}


@d Bucket Sorter Class Interface @{
template <typename BucketMap, typename ValueIndexMap>
class bucket_sorter {
public:
  typedef typename property_traits<BucketMap>::value_type bucket_type;
  typedef typename property_traits<ValueIndex>::key_type value_type;
  typedef typename property_traits<ValueIndex>::value_type size_type;

  bucket_sorter(size_type length, bucket_type max_bucket,
                const BucketMap& bucket = BucketMap(),
                const ValueIndexMap& index_map = ValueIndexMap());
  void remove(const value_type& x);
  void push(const value_type& x);
  void update(const value_type& x);

  class stack {
  public:
    void push(const value_type& x);
    void pop();
    value_type& top();
    const value_type& top() const;
    bool empty() const;
  private:
    @<Bucket Stack Constructor@>
    @<Bucket Stack Data Members@>
  };
  stack operator[](const bucket_type& i);
private:
  @<Bucket Sorter Data Members@>
};
@}

\code{BucketMap} is a \concept{LvaluePropertyMap} that converts a
value object to a bucket number (an integer). The range of the mapping
must be finite. \code{ValueIndexMap} is a \concept{LvaluePropertyMap}
that maps from value objects to a unique integer. At the top of the
definition of \code{bucket\_sorter} we create some typedefs for the
bucket number type, the value type, and the index type.

@d Bucket Sorter Data Members @{
std::vector<size_type>   head;
std::vector<size_type>   next;
std::vector<size_type>   prev;
std::vector<value_type>  id_to_value;
BucketMap bucket_map;
ValueIndexMap index_map;
@}


\code{N} is the maximum integer that the \code{index\_map} will map a
value object to (the minimum is assumed to be zero).

@d Bucket Sorter Constructor @{
bucket_sorter::bucket_sorter
  (size_type N, bucket_type max_bucket,
   const BucketMap& bucket_map = BucketMap(),
   const ValueIndexMap& index_map = ValueIndexMap())
  : head(max_bucket, invalid_value()),
    next(N, invalid_value()),
    prev(N, invalid_value()),
    id_to_value(N),
    bucket_map(bucket_map), index_map(index_map) { }
@}


\bibliographystyle{abbrv}
\bibliography{jtran,ggcl,optimization,generic-programming,cad}

\end{document}