1 /*****************************************************************************
2 /
3 / SPACE (SPArse Cholesky Elimination) Library: ms.c
4 /
5 / author J"urgen Schulze, University of Paderborn
6 / created 01jan04
7 /
8 / This file contains functions dealing with the multisector object
9 /
10 ******************************************************************************
11
12 Data type: struct multisector
13 graph_t *G; pointer to original graph
14 int *stage; stage[u]=i => node u will be elim. in stage i
15 int nstages; number of stages
16 int nnodes; number of nodes in multisector
17 int totmswght; weigth of nodes in multisector
18 Comments:
19 o Structure does not own graph object G => it will not be freed
20 Note: G is the original graph
21 Methods in lib/multisector.c:
22 - ms = newMultisector(graph_t *G);
23 o Initial: nstages = nnodes = totmswght = 0;
24 - void freeMultisector(ms_t *ms);
25 - ms = trivialMultisector(graph_t *G);
26 o allocates memory for the multisector object by a call to newMultisector
27 and sets stage[u] = 0 for all vertices u and nstages = 1; the trivial
28 multisector can be used for pure bottom-up orderings
29 - ms = constructMultisector(graph_t *G, options_t* options, timings_t *cpus);
30 o MASTER_FUNCTION: computes a multisector for G according to the specified
31 ordtype e { MINIMUM_PRIORITY, INCOMPLETE_ND, MULTISECTION,
32 TRISTAGE_MULTISECTION }
33 MINIMUM_PRIORTY:
34 return the multisector obtained by a call to trivialMultisector
35 INCOMPLETE_ND, MULTISECTION, TRISTAGE_MULTISECTION:
36 build separator tree by calling buildNDtree and extract multisector
37 by calling extractMS2stage (MULTISECTION) or extractMSmultistage
38 (INCOMPLETE_ND, TRISTAGE_MULTISECTION)
39 o used options: (also see buildNDtree)
40 OPTION_ORDTYPE, OPTION_DOMAIN_SIZE, OPTION_MSGLVL, OPTION_NODE_SELECTION3
41 o returned timings: (see buildNDtree)
42 TIME_INITDOMDEC, TIME_COARSEDOMDEC, TIME_INITSEP, TIME_REFINESEP
43 TIME_MULTILEVEL, TIME_SMOOTH
44 - ms = extractMS2stage(nestdiss_t *ndroot);
45 o extracts a 2-stage multisector from the nested dissection tree with root
46 ndroot: stage[u] = 0 => u belongs to a domain
47 stage[u] = 1 => u belongs to the multisector
48 and nstages = 2; the 2-stage multisector can be used for classical
49 multisection orderings
50 - ms = extractMSmultistage(nestdiss_t *ndroot);
51 o extracts a multi-stage multisector from the nested dissection tree at
52 ndroot: stage[u] = 0 => u belongs to a domain
53 stage[u] = i, i > 0 => u belongs to the multisector, i.e.:
54 stage[u] = 1 => u belongs to a leaf separator
55 :
56 stage[u] = nstages-1 => u belongs to the root separator
57 the multisector can be used for incomplete nested dissection orderings
58 or for three-stage multisection orderings
59
60 ******************************************************************************/
61
62 #include <space.h>
63
64
65 /*****************************************************************************
66 ******************************************************************************/
67 multisector_t*
newMultisector(graph_t * G)68 newMultisector(graph_t *G)
69 { multisector_t *ms;
70
71 mymalloc(ms, 1, multisector_t);
72 mymalloc(ms->stage, G->nvtx, PORD_INT);
73
74 ms->G = G;
75 ms->nstages = 0;
76 ms->nnodes = 0;
77 ms->totmswght = 0;
78
79 return(ms);
80 }
81
82
83 /*****************************************************************************
84 ******************************************************************************/
85 void
freeMultisector(multisector_t * ms)86 freeMultisector(multisector_t *ms)
87 {
88 free(ms->stage);
89 free(ms);
90 }
91
92
93 /*****************************************************************************
94 ******************************************************************************/
95 multisector_t*
trivialMultisector(graph_t * G)96 trivialMultisector(graph_t *G)
97 { multisector_t *ms;
98 PORD_INT *stage, nvtx, u;
99
100 /* -----------------------------------------------------------------
101 allocate memory for the multisector object and init. stage vector
102 ----------------------------------------------------------------- */
103 nvtx = G->nvtx;
104 ms = newMultisector(G);
105 stage = ms->stage;
106
107 for (u = 0; u < nvtx; u++)
108 stage[u] = 0; /* no vertex belongs to a separator */
109
110 /* -------------------------------
111 finalize the multisector object
112 ------------------------------- */
113 ms->nstages = 1;
114 ms->nnodes = 0;
115 ms->totmswght = 0;
116
117 return(ms);
118 }
119
120
121 /*****************************************************************************
122 ******************************************************************************/
123 multisector_t*
constructMultisector(graph_t * G,options_t * options,timings_t * cpus)124 constructMultisector(graph_t *G, options_t* options, timings_t *cpus)
125 { multisector_t *ms;
126 nestdiss_t *ndroot;
127 PORD_INT *map, nvtx, ordtype;
128
129 nvtx = G->nvtx;
130
131 /* ------------------------------
132 check number of nodes in graph
133 ------------------------------ */
134 /* -----------------------------------
135 JY: inserted the condition
136 "&& (options[OPTION_MSGLVL] > 0)"
137 below, to avoid systematic printing
138 ----------------------------------- */
139 if ((nvtx <= MIN_NODES) && (options[OPTION_ORDTYPE] != MINIMUM_PRIORITY)
140 && (options[OPTION_MSGLVL] > 0))
141 { printf("\nWarning in constructMultisector\n"
142 " graph has less than %d nodes, skipping separator construction\n\n",
143 MIN_NODES);
144 options[OPTION_ORDTYPE] = MINIMUM_PRIORITY;
145 }
146 /* --------------------------------------------------------
147 determine the multisector according to the ordering type
148 -------------------------------------------------------- */
149 ordtype = options[OPTION_ORDTYPE];
150 switch(ordtype)
151 { case MINIMUM_PRIORITY:
152 ms = trivialMultisector(G);
153 break;
154
155 case INCOMPLETE_ND:
156 case MULTISECTION:
157 case TRISTAGE_MULTISECTION:
158 mymalloc(map, nvtx, PORD_INT);
159 ndroot = setupNDroot(G, map);
160 buildNDtree(ndroot, options, cpus);
161 if (ordtype == MULTISECTION)
162 ms = extractMS2stage(ndroot);
163 else
164 ms = extractMSmultistage(ndroot);
165 freeNDtree(ndroot);
166 freeNDnode(ndroot);
167 free(map);
168 break;
169
170 default:
171 fprintf(stderr, "\nError in function constructMultisector\n"
172 " unrecognized ordering type %d\n", ordtype);
173 quit();
174 }
175 return(ms);
176 }
177
178
179 /*****************************************************************************
180 ******************************************************************************/
181 multisector_t*
extractMS2stage(nestdiss_t * ndroot)182 extractMS2stage(nestdiss_t *ndroot)
183 { multisector_t *ms;
184 nestdiss_t *nd, *parent;
185 PORD_INT *stage, *intvertex, *intcolor;
186 PORD_INT nvint, nnodes, totmswght, i;
187
188 /* -----------------------------------------------------------------
189 allocate memory for the multisector object and init. stage vector
190 ----------------------------------------------------------------- */
191 ms = trivialMultisector(ndroot->G);
192 stage = ms->stage;
193
194 /* ------------------------------------------------------------
195 extract the stages of the separator vertices:
196 stage[u] = 1, iff u belongs to a separator
197 ------------------------------------------------------------ */
198 nnodes = totmswght = 0;
199 for (nd = ndroot; nd->childB != NULL; nd = nd->childB);
200 while (nd != ndroot)
201 { parent = nd->parent;
202 if ((parent == NULL) || (parent->childB == NULL)
203 || (parent->childW == NULL))
204 { fprintf(stderr, "\nError in function extractMS2stage\n"
205 " nested dissection tree corrupted\n");
206 quit();
207 }
208 if (parent->childB == nd) /* left subtree of parent visited */
209 for (nd = parent->childW; nd->childB != NULL; nd = nd->childB);
210 else /* right subtree of parent visited */
211 { nd = parent; /* extract the separator of parent */
212 totmswght += nd->cwght[GRAY];
213 nvint = nd->nvint;
214 intvertex = nd->intvertex;
215 intcolor = nd->intcolor;
216 for (i = 0; i < nvint; i++)
217 if (intcolor[i] == GRAY)
218 { nnodes++;
219 stage[intvertex[i]] = 1;
220 }
221 }
222 }
223
224 /* ------------------------------------------
225 finalize the multisector object and return
226 ------------------------------------------ */
227 ms->nstages = 2;
228 ms->nnodes = nnodes;
229 ms->totmswght = totmswght;
230
231 return(ms);
232 }
233
234
235 /*****************************************************************************
236 ******************************************************************************/
237 multisector_t*
extractMSmultistage(nestdiss_t * ndroot)238 extractMSmultistage(nestdiss_t *ndroot)
239 { multisector_t *ms;
240 nestdiss_t *nd, *parent;
241 PORD_INT *stage, *intvertex, *intcolor;
242 PORD_INT nvtx, nvint, maxstage, istage, nnodes, totmswght, i, u;
243
244 /* -----------------------------------------------------------------
245 allocate memory for the multisector object and init. stage vector
246 ----------------------------------------------------------------- */
247 ms = trivialMultisector(ndroot->G);
248 stage = ms->stage;
249
250 /* ------------------------------------------------------------
251 extract the stages of the separator vertices:
252 stage[u] = i, i>0, iff u belongs to a separator in depth i-1
253 ------------------------------------------------------------ */
254 maxstage = nnodes = totmswght = 0;
255 for (nd = ndroot; nd->childB != NULL; nd = nd->childB);
256 while (nd != ndroot)
257 { parent = nd->parent;
258 if ((parent == NULL) || (parent->childB == NULL)
259 || (parent->childW == NULL))
260 { fprintf(stderr, "\nError in function extractMSmultistage\n"
261 " nested dissection tree corrupted\n");
262 quit();
263 }
264 if (parent->childB == nd) /* left subtree of parent visited */
265 for (nd = parent->childW; nd->childB != NULL; nd = nd->childB);
266 else /* right subtree of parent visited */
267 { nd = parent; /* extract the separator of parent */
268 istage = nd->depth + 1; /* sep. vertices belong to this stage */
269 maxstage = max(maxstage, istage);
270 totmswght += nd->cwght[GRAY];
271 nvint = nd->nvint;
272 intvertex = nd->intvertex;
273 intcolor = nd->intcolor;
274 for (i = 0; i < nvint; i++)
275 if (intcolor[i] == GRAY)
276 { nnodes++;
277 stage[intvertex[i]] = istage;
278 }
279 }
280 }
281
282 /* --------------------------------------------------------------------
283 we have: stage[u] = 0 => u belongs to a domain
284 stage[u] = 1 => u belongs to the root separator (depth = 0)
285 :
286 stage[u] = maxstage => u belongs to a leaf separator
287 but we must eliminate the separators in a bottom-up fashion; we like
288 to have: stage[u] = 0 => u belongs to a domain
289 stage[u] = 1 => u belongs to a leaf separator
290 :
291 stage[u] = maxstage => u belongs to the root separator
292 -------------------------------------------------------------------- */
293 nvtx = ndroot->G->nvtx;
294 for (u = 0; u < nvtx; u++)
295 if (stage[u] > 0)
296 stage[u] = maxstage - stage[u] + 1;
297
298 /* ------------------------------------------
299 finalize the multisector object and return
300 ------------------------------------------ */
301 ms->nstages = maxstage + 1;
302 ms->nnodes = nnodes;
303 ms->totmswght = totmswght;
304
305 return(ms);
306 }
307