1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
<HTML>
<!--
-- Copyright (c) Lie-Quan Lee and Jeremy Siek, 2001
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Boost Graph Library: Minimum Degree Ordering</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../c++boost.gif"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1><A NAME="sec:mmd">
<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>,
and <a href="./MutableIncidenceGraph.html">Mutable Incidence 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/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/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/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/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/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="../../../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="../../../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>
|
