[ceph.git] / ceph / src / boost / libs / graph / doc / minimum_degree_ordering.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 &lt;class AdjacencyGraph, class OutDegreeMap,
           class InversePermutationMap, 
           class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap&gt;
  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&nbsp;[<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 &quot;fill-in&quot;, 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 &quot;good enough&quot; 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&amp; G</tt> &nbsp;(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> &nbsp(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> &nbsp(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> &nbsp(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> &nbsp(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> &nbsp(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> &nbsp(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&nbsp;[<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 &copy; 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>
Commit	Line	Data
7c673cae FG	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 <class AdjacencyGraph, class OutDegreeMap,
	26	class InversePermutationMap,
	27	class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap>
	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 [<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 "fill-in", 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 "good enough" 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& G</tt>  (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 [<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 © 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>