]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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} |