1 /* stages.c */
2
3 #include "../DSTree.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 -------------------------------------------------------
10 create a stages vector for a nested dissection ordering
11
12 created -- 96mar10, cca
13 -------------------------------------------------------
14 */
15 IV *
DSTree_NDstages(DSTree * dstree)16 DSTree_NDstages (
17 DSTree *dstree
18 ) {
19 int ndomsep, nvtx, v ;
20 int *hmetric, *map, *stages ;
21 IV *hmetricIV, *mapIV, *stagesIV, *vmetricIV ;
22 Tree *tree ;
23 /*
24 --------------
25 check the data
26 --------------
27 */
28 if ( dstree == NULL
29 || (tree = dstree->tree) == NULL
30 || (ndomsep = tree->n) < 1
31 || (mapIV = dstree->mapIV) == NULL ) {
32 fprintf(stderr, "\n fatal error in DSTree_NDstages(%p)"
33 "\n bad input\n", dstree) ;
34 exit(-1) ;
35 }
36 IV_sizeAndEntries(mapIV, &nvtx, &map) ;
37 if ( map == NULL || nvtx < 1 ) {
38 fprintf(stderr, "\n fatal error in DSTree_NDstages(%p)"
39 "\n bad mapIV object\n", dstree) ;
40 exit(-1) ;
41 }
42 /*
43 ----------------------------------
44 get the height metric for the tree
45 ----------------------------------
46 */
47 vmetricIV = IV_new() ;
48 IV_init(vmetricIV, ndomsep, NULL) ;
49 IV_fill(vmetricIV, 1) ;
50 hmetricIV = Tree_setHeightImetric(tree, vmetricIV) ;
51 hmetric = IV_entries(hmetricIV) ;
52 /*
53 ------------------------------------
54 set the stages for nested dissection
55 ------------------------------------
56 */
57 stagesIV = IV_new() ;
58 IV_init(stagesIV, nvtx, NULL) ;
59 stages = IV_entries(stagesIV) ;
60 for ( v = 0 ; v < nvtx ; v++ ) {
61 stages[v] = hmetric[map[v]] - 1 ;
62 }
63 /*
64 ------------------------
65 free the working storage
66 ------------------------
67 */
68 IV_free(vmetricIV) ;
69 IV_free(hmetricIV) ;
70
71 return(stagesIV) ; }
72
73 /*--------------------------------------------------------------------*/
74 /*
75 ----------------------------------------------------------------
76 create a stages vector for a ``half'' nested dissection ordering
77
78 created -- 96mar10, cca
79 ----------------------------------------------------------------
80 */
81 IV *
DSTree_ND2stages(DSTree * dstree)82 DSTree_ND2stages (
83 DSTree *dstree
84 ) {
85 int ndomsep, nvtx, v ;
86 int *hmetric, *map, *stages ;
87 IV *hmetricIV, *mapIV, *stagesIV, *vmetricIV ;
88 Tree *tree ;
89 /*
90 --------------
91 check the data
92 --------------
93 */
94 if ( dstree == NULL
95 || (tree = dstree->tree) == NULL
96 || (ndomsep = tree->n) < 1
97 || (mapIV = dstree->mapIV) == NULL ) {
98 fprintf(stderr, "\n fatal error in DSTree_ND2stages(%p)"
99 "\n bad input\n", dstree) ;
100 exit(-1) ;
101 }
102 IV_sizeAndEntries(mapIV, &nvtx, &map) ;
103 if ( map == NULL || nvtx < 1 ) {
104 fprintf(stderr, "\n fatal error in DSTree_ND2stages(%p)"
105 "\n bad mapIV object\n", dstree) ;
106 exit(-1) ;
107 }
108 /*
109 ----------------------------------
110 get the height metric for the tree
111 ----------------------------------
112 */
113 vmetricIV = IV_new() ;
114 IV_init(vmetricIV, ndomsep, NULL) ;
115 IV_fill(vmetricIV, 1) ;
116 hmetricIV = Tree_setHeightImetric(tree, vmetricIV) ;
117 hmetric = IV_entries(hmetricIV) ;
118 /*
119 ------------------------------------
120 set the stages for nested dissection
121 ------------------------------------
122 */
123 stagesIV = IV_new() ;
124 IV_init(stagesIV, nvtx, NULL) ;
125 stages = IV_entries(stagesIV) ;
126 for ( v = 0 ; v < nvtx ; v++ ) {
127 stages[v] = hmetric[map[v]] - 1 ;
128 if ( stages[v] > 0 ) {
129 stages[v] = (1 + stages[v])/2 ;
130 }
131 }
132 /*
133 ------------------------
134 free the working storage
135 ------------------------
136 */
137 IV_free(vmetricIV) ;
138 IV_free(hmetricIV) ;
139
140 return(stagesIV) ; }
141
142 /*--------------------------------------------------------------------*/
143 /*
144 ------------------------------------------------------------
145 create a stages vector for a two-level multisection ordering
146
147 created -- 96mar10, cca
148 ------------------------------------------------------------
149 */
150 IV *
DSTree_MS2stages(DSTree * dstree)151 DSTree_MS2stages (
152 DSTree *dstree
153 ) {
154 int ndomsep, nvtx, v ;
155 int *hmetric, *map, *stages ;
156 IV *hmetricIV, *mapIV, *stagesIV, *vmetricIV ;
157 Tree *tree ;
158 /*
159 --------------
160 check the data
161 --------------
162 */
163 if ( dstree == NULL
164 || (tree = dstree->tree) == NULL
165 || (ndomsep = tree->n) < 1
166 || (mapIV = dstree->mapIV) == NULL ) {
167 fprintf(stderr, "\n fatal error in DSTree_MS2stages(%p)"
168 "\n bad input\n", dstree) ;
169 exit(-1) ;
170 }
171 IV_sizeAndEntries(mapIV, &nvtx, &map) ;
172 if ( map == NULL || nvtx < 1 ) {
173 fprintf(stderr, "\n fatal error in DSTree_MS2stages(%p)"
174 "\n bad mapIV object\n", dstree) ;
175 exit(-1) ;
176 }
177 /*
178 ----------------------------------
179 get the height metric for the tree
180 ----------------------------------
181 */
182 vmetricIV = IV_new() ;
183 IV_init(vmetricIV, ndomsep, NULL) ;
184 IV_fill(vmetricIV, 1) ;
185 hmetricIV = Tree_setHeightImetric(tree, vmetricIV) ;
186 hmetric = IV_entries(hmetricIV) ;
187 /*
188 -----------------------------------------
189 set the stages for two-level multisection
190 -----------------------------------------
191 */
192 stagesIV = IV_new() ;
193 IV_init(stagesIV, nvtx, NULL) ;
194 stages = IV_entries(stagesIV) ;
195 for ( v = 0 ; v < nvtx ; v++ ) {
196 stages[v] = hmetric[map[v]] - 1 ;
197 if ( stages[v] > 0 ) {
198 stages[v] = 1 ;
199 }
200 }
201 /*
202 ------------------------
203 free the working storage
204 ------------------------
205 */
206 IV_free(vmetricIV) ;
207 IV_free(hmetricIV) ;
208
209 return(stagesIV) ; }
210
211 /*--------------------------------------------------------------------*/
212 /*
213 --------------------------------------------------------------
214 create a stages vector for a three-level multisection ordering
215
216 created -- 96mar10, cca
217 --------------------------------------------------------------
218 */
219 IV *
DSTree_MS3stages(DSTree * dstree)220 DSTree_MS3stages (
221 DSTree *dstree
222 ) {
223 int ndomsep, nstage, nvtx, v ;
224 int *hmetric, *map, *stages ;
225 IV *hmetricIV, *mapIV, *stagesIV, *vmetricIV ;
226 Tree *tree ;
227 /*
228 --------------
229 check the data
230 --------------
231 */
232 if ( dstree == NULL
233 || (tree = dstree->tree) == NULL
234 || (ndomsep = tree->n) < 1
235 || (mapIV = dstree->mapIV) == NULL ) {
236 fprintf(stderr, "\n fatal error in DSTree_MS3stages(%p)"
237 "\n bad input\n", dstree) ;
238 exit(-1) ;
239 }
240 IV_sizeAndEntries(mapIV, &nvtx, &map) ;
241 if ( map == NULL || nvtx < 1 ) {
242 fprintf(stderr, "\n fatal error in DSTree_MS3stages(%p)"
243 "\n bad mapIV object\n", dstree) ;
244 exit(-1) ;
245 }
246 /*
247 ----------------------------------
248 get the height metric for the tree
249 ----------------------------------
250 */
251 vmetricIV = IV_new() ;
252 IV_init(vmetricIV, ndomsep, NULL) ;
253 IV_fill(vmetricIV, 1) ;
254 hmetricIV = Tree_setHeightImetric(tree, vmetricIV) ;
255 hmetric = IV_entries(hmetricIV) ;
256 nstage = IV_max(hmetricIV) ;
257 /*
258 -------------------------------------------
259 set the stages for three-level multisection
260 -------------------------------------------
261 */
262 stagesIV = IV_new() ;
263 IV_init(stagesIV, nvtx, NULL) ;
264 stages = IV_entries(stagesIV) ;
265 for ( v = 0 ; v < nvtx ; v++ ) {
266 stages[v] = hmetric[map[v]] - 1 ;
267 if ( stages[v] > 0 ) {
268 if ( 2*stages[v] > nstage ) {
269 stages[v] = 2 ;
270 } else {
271 stages[v] = 1 ;
272 }
273 }
274 }
275 /*
276 ------------------------
277 free the working storage
278 ------------------------
279 */
280 IV_free(vmetricIV) ;
281 IV_free(hmetricIV) ;
282
283 return(stagesIV) ; }
284
285 /*--------------------------------------------------------------------*/
286 /*
287 ---------------------------------------------------
288 create a stages vector via cutoff on domain weights
289
290 created -- 97jun12, cca
291 ---------------------------------------------------
292 */
293 IV *
DSTree_stagesViaDomainWeight(DSTree * dstree,int * vwghts,DV * cutoffDV)294 DSTree_stagesViaDomainWeight (
295 DSTree *dstree,
296 int *vwghts,
297 DV *cutoffDV
298 ) {
299 double totvwght ;
300 double *cutoffs, *nodewghts, *subtreewghts ;
301 DV *nodewghtDV, *subtreeDV ;
302 int ireg, istage, jstage, ndomsep, nstage, nvtx, v ;
303 int *map, *mark, *regmap, *stages ;
304 IV *mapIV, *stagesIV ;
305 Tree *tree ;
306 /*
307 --------------
308 check the data
309 --------------
310 */
311 if ( dstree == NULL
312 || (tree = dstree->tree) == NULL
313 || (ndomsep = tree->n) < 1
314 || (mapIV = dstree->mapIV) == NULL
315 || cutoffDV == NULL ) {
316 fprintf(stderr,
317 "\n fatal error in DSTree_stagesViaDomainWeight(%p,%p,%p)"
318 "\n bad input\n", dstree, vwghts, cutoffDV) ;
319 exit(-1) ;
320 }
321 IV_sizeAndEntries(mapIV, &nvtx, &map) ;
322 if ( map == NULL || nvtx < 1 ) {
323 fprintf(stderr,
324 "\n fatal error in DSTree_stagesViaDomainWeight(%p,%p,%p)"
325 "\n bad mapIV object\n", dstree, vwghts, cutoffDV) ;
326 exit(-1) ;
327 }
328 DV_sizeAndEntries(cutoffDV, &nstage, &cutoffs) ;
329 if ( cutoffs == NULL || nstage < 1 ) {
330 fprintf(stderr,
331 "\n fatal error in DSTree_stagesViaDomainWeight(%p,%p,%p)"
332 "\n bad cutoffDV object\n", dstree, vwghts, cutoffDV) ;
333 exit(-1) ;
334 }
335 #if MYDEBUG > 0
336 fprintf(stdout, "\n %d stages", nstage) ;
337 DVfprintf(stdout, nstage, cutoffs) ;
338 #endif
339 /*
340 --------------------------------
341 get the node metric for the tree
342 --------------------------------
343 */
344 nodewghtDV = DV_new() ;
345 DV_init(nodewghtDV, ndomsep, NULL) ;
346 DV_fill(nodewghtDV, 0.0) ;
347 nodewghts = DV_entries(nodewghtDV) ;
348 totvwght = 0.0 ;
349 if ( vwghts == NULL ) {
350 for ( v = 0 ; v < nvtx ; v++ ) {
351 nodewghts[map[v]]++ ;
352 }
353 totvwght = nvtx ;
354 } else {
355 for ( v = 0 ; v < nvtx ; v++ ) {
356 nodewghts[map[v]] += vwghts[v] ;
357 totvwght += vwghts[v] ;
358 }
359 }
360 #if MYDEBUG > 0
361 fprintf(stdout, "\n\n node metric") ;
362 DV_writeForHumanEye(nodewghtDV, stdout) ;
363 #endif
364 /*
365 ----------------------------------
366 get the subtree metric for the tree
367 ----------------------------------
368 */
369 subtreeDV = Tree_setSubtreeDmetric(tree, nodewghtDV) ;
370 subtreewghts = DV_entries(subtreeDV) ;
371 #if MYDEBUG > 0
372 fprintf(stdout, "\n\n subtree metric before scale") ;
373 DV_writeForHumanEye(subtreeDV, stdout) ;
374 #endif
375 for ( ireg = 0 ; ireg < ndomsep ; ireg++ ) {
376 subtreewghts[ireg] /= totvwght ;
377 }
378 #if MYDEBUG > 0
379 fprintf(stdout, "\n\n subtree metric after scale") ;
380 DV_writeForHumanEye(subtreeDV, stdout) ;
381 #endif
382 /*
383 ----------------------------
384 mark all stages with support
385 ----------------------------
386 */
387 mark = IVinit(nstage, -1) ;
388 for ( ireg = 0 ; ireg < ndomsep ; ireg++ ) {
389 #if MYDEBUG > 0
390 fprintf(stdout, "\n region %d, subtree weight %.4f",
391 ireg, subtreewghts[ireg]) ;
392 fflush(stdout) ;
393 #endif
394 for ( istage = 0 ; istage < nstage - 1 ; istage++ ) {
395 if ( cutoffs[istage] <= subtreewghts[ireg]
396 && subtreewghts[ireg] < cutoffs[istage+1] ) {
397 mark[istage] = 1 ;
398 #if MYDEBUG > 0
399 fprintf(stdout, ", found in stage %d", istage) ;
400 fflush(stdout) ;
401 #endif
402 break ;
403 }
404 }
405 if ( istage == nstage - 1 ) {
406 mark[nstage - 1] = 1 ;
407 }
408 }
409 /*
410 ------------------
411 slide cutoffs down
412 ------------------
413 */
414 for ( istage = jstage = 0 ; istage < nstage ; istage++ ) {
415 if ( mark[istage] == 1 ) {
416 #if MYDEBUG > 0
417 fprintf(stdout, "\n stage %d marked", istage) ;
418 fflush(stdout) ;
419 #endif
420 cutoffs[jstage++] = cutoffs[istage] ;
421 }
422 }
423 nstage = jstage ;
424 /*
425 ----------------------------------
426 get the map from regions to stages
427 ----------------------------------
428 */
429 regmap = IVinit(ndomsep, -1) ;
430 for ( ireg = 0 ; ireg < ndomsep ; ireg++ ) {
431 #if MYDEBUG > 0
432 fprintf(stdout, "\n region %d, subtree weight %.4f",
433 ireg, subtreewghts[ireg]) ;
434 fflush(stdout) ;
435 #endif
436 for ( istage = 0 ; istage < nstage - 1 ; istage++ ) {
437 if ( cutoffs[istage] <= subtreewghts[ireg]
438 && subtreewghts[ireg] < cutoffs[istage+1] ) {
439 #if MYDEBUG > 0
440 fprintf(stdout, ", found in stage %d", istage) ;
441 fflush(stdout) ;
442 #endif
443 regmap[ireg] = istage ;
444 break ;
445 }
446 }
447 if ( istage == nstage - 1 ) {
448 regmap[ireg] = nstage - 1 ;
449 #if MYDEBUG > 0
450 fprintf(stdout, ", found in stage %d", nstage - 1) ;
451 fflush(stdout) ;
452 #endif
453 }
454 }
455 #if MYDEBUG > 0
456 fprintf(stdout, "\n\n region to stage map") ;
457 IVfp80(stdout, ndomsep, regmap, 80, &ierr) ;
458 #endif
459 /*
460 --------------
461 set the stages
462 --------------
463 */
464 stagesIV = IV_new() ;
465 IV_init(stagesIV, nvtx, NULL) ;
466 stages = IV_entries(stagesIV) ;
467 for ( v = 0 ; v < nvtx ; v++ ) {
468 stages[v] = regmap[map[v]] ;
469 }
470 #if MYDEBUG > 0
471 stageWeights = DVinit(nstage, 0.0) ;
472 for ( ireg = 0 ; ireg < ndomsep ; ireg++ ) {
473 stageWeights[regmap[ireg]] += nodewghts[ireg] ;
474 }
475 fprintf(stdout, "\n\n stageWeights, sum = %.4f",
476 DVsum(nstage, stageWeights)) ;
477 DVfprintf(stdout, nstage, stageWeights) ;
478 for ( istage = nstage - 2 ; istage >= 0 ; istage-- ) {
479 stageWeights[istage] += stageWeights[istage+1] ;
480 }
481 fprintf(stdout, "\n\n stageWeights, sum = %.4f",
482 DVsum(nstage, stageWeights)) ;
483 for ( istage = 0 ; istage < nstage ; istage++ ) {
484 stageWeights[istage] /= totvwght ;
485 }
486 fprintf(stdout, "\n\n stageWeights, sum = %.4f",
487 DVsum(nstage, stageWeights)) ;
488 DVfprintf(stdout, nstage, stageWeights) ;
489 DVfree(stageWeights) ;
490 #endif
491 /*
492 ------------------------
493 free the working storage
494 ------------------------
495 */
496 DV_free(nodewghtDV) ;
497 DV_free(subtreeDV) ;
498 IVfree(regmap) ;
499 IVfree(mark) ;
500
501 return(stagesIV) ; }
502
503 /*--------------------------------------------------------------------*/
504