179 lines
6.7 KiB
HTML
179 lines
6.7 KiB
HTML
<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>
|