1 /* permute.c */
2
3 #include "../FrontMtx.h"
4
5 /*--------------------------------------------------------------------*/
6 static void FrontMtx_reorderRowIndices ( FrontMtx *frontmtx, int J,
7 int K, int map[], int msglvl, FILE *msgFile ) ;
8 static void FrontMtx_reorderColumnIndices ( FrontMtx *frontmtx, int J,
9 int K, int map[], int msglvl, FILE *msgFile ) ;
10 /*--------------------------------------------------------------------*/
11 /*
12 ------------------------------------------------------------------
13 purpose -- permute the upper adjacency structure so that the
14 indices in bnd{J} are in ascending order w.r.t. their ancestors
15
16 created -- 98mar05, cca
17 ------------------------------------------------------------------
18 */
19 void
FrontMtx_permuteUpperAdj(FrontMtx * frontmtx,int msglvl,FILE * msgFile)20 FrontMtx_permuteUpperAdj (
21 FrontMtx *frontmtx,
22 int msglvl,
23 FILE *msgFile
24 ) {
25 int J, K, neqns ;
26 int *map, *par ;
27 Tree *tree ;
28 /*
29 ---------------
30 check the input
31 ---------------
32 */
33 if ( frontmtx == NULL || (msglvl > 0 && msgFile == NULL) ) {
34 fprintf(stderr,
35 "\n fatal error in FrontMtx_permuteUpperAdj(%p,%d,%p)"
36 "\n badn input\n", frontmtx, msglvl, msgFile) ;
37 exit(-1) ;
38 }
39 neqns = FrontMtx_neqns(frontmtx) ;
40 map = IVinit(neqns, -1) ;
41 tree = FrontMtx_frontTree(frontmtx) ;
42 par = tree->par ;
43 for ( J = Tree_preOTfirst(tree) ;
44 J != -1 ;
45 J = Tree_preOTnext(tree, J) ) {
46 if ( (K = par[J]) != -1 ) {
47 FrontMtx_reorderColumnIndices(frontmtx, J, K, map,
48 msglvl, msgFile) ;
49 }
50 }
51 IVfree(map) ;
52
53 return ; }
54
55 /*--------------------------------------------------------------------*/
56 /*
57 ------------------------------------------------------------------
58 purpose -- permute the lower adjacency structure so that the
59 indices in bnd{J} are in ascending order w.r.t. their ancestors
60
61 created -- 98mar05, cca
62 ------------------------------------------------------------------
63 */
64 void
FrontMtx_permuteLowerAdj(FrontMtx * frontmtx,int msglvl,FILE * msgFile)65 FrontMtx_permuteLowerAdj (
66 FrontMtx *frontmtx,
67 int msglvl,
68 FILE *msgFile
69 ) {
70 int J, K, neqns ;
71 int *map, *par ;
72 Tree *tree ;
73 /*
74 ---------------
75 check the input
76 ---------------
77 */
78 if ( frontmtx == NULL || (msglvl > 0 && msgFile == NULL) ) {
79 fprintf(stderr,
80 "\n fatal error in FrontMtx_permuteLowerAdj(%p,%d,%p)"
81 "\n badn input\n", frontmtx, msglvl, msgFile) ;
82 exit(-1) ;
83 }
84 neqns = FrontMtx_neqns(frontmtx) ;
85 map = IVinit(neqns, -1) ;
86 tree = FrontMtx_frontTree(frontmtx) ;
87 par = tree->par ;
88 for ( J = Tree_preOTfirst(tree) ;
89 J != -1 ;
90 J = Tree_preOTnext(tree, J) ) {
91 if ( (K = par[J]) != -1 ) {
92 FrontMtx_reorderRowIndices(frontmtx, J, K, map,
93 msglvl, msgFile) ;
94 }
95 }
96 IVfree(map) ;
97
98 return ; }
99
100 /*--------------------------------------------------------------------*/
101 /*
102 ------------------------------------------------------------
103 purpose -- if the columns indices of the front matrix are in
104 different order than the column indices of U_{J,bnd{J}},
105 sort the columns of U_{J,bnd{J}} into ascending order
106 w.r.t the column indices of the front matrix.
107
108 created -- 98mar05, cca
109 ------------------------------------------------------------
110 */
111 void
FrontMtx_permuteUpperMatrices(FrontMtx * frontmtx,int msglvl,FILE * msgFile)112 FrontMtx_permuteUpperMatrices (
113 FrontMtx *frontmtx,
114 int msglvl,
115 FILE *msgFile
116 ) {
117 SubMtx *mtxUJ ;
118 int ii, jj, J, mustdo, neqns, nfront, ncolJ, ncolUJ, nJ ;
119 int *map, *colindJ, *colindUJ ;
120 /*
121 ---------------
122 check the input
123 ---------------
124 */
125 if ( frontmtx == NULL || (msglvl > 0 && msgFile == NULL) ) {
126 fprintf(stderr,
127 "\n fatal error in FrontMtx_permuteUpperMatrices(%p,%d,%p)"
128 "\n badn input\n", frontmtx, msglvl, msgFile) ;
129 exit(-1) ;
130 }
131 nfront = FrontMtx_nfront(frontmtx) ;
132 neqns = FrontMtx_neqns(frontmtx) ;
133 map = IVinit(neqns, -1) ;
134 for ( J = 0 ; J < nfront ; J++ ) {
135 mtxUJ = FrontMtx_upperMtx(frontmtx, J, nfront) ;
136 if ( mtxUJ != NULL ) {
137 nJ = FrontMtx_frontSize(frontmtx, J) ;
138 FrontMtx_columnIndices(frontmtx, J, &ncolJ, &colindJ) ;
139 SubMtx_columnIndices(mtxUJ, &ncolUJ, &colindUJ) ;
140 for ( ii = nJ, jj = mustdo = 0 ; ii < ncolJ ; ii++, jj++ ) {
141 if ( colindJ[ii] != colindUJ[jj] ) {
142 mustdo = 1 ; break ;
143 }
144 }
145 if ( mustdo == 1 ) {
146 for ( ii = 0 ; ii < ncolJ ; ii++ ) {
147 map[colindJ[ii]] = ii ;
148 }
149 for ( ii = 0 ; ii < ncolUJ ; ii++ ) {
150 colindUJ[ii] = map[colindUJ[ii]] ;
151 }
152 SubMtx_sortColumnsUp(mtxUJ) ;
153 for ( ii = 0 ; ii < ncolUJ ; ii++ ) {
154 colindUJ[ii] = colindJ[colindUJ[ii]] ;
155 }
156 }
157 }
158 }
159 IVfree(map) ;
160
161 return ; }
162
163 /*--------------------------------------------------------------------*/
164 /*
165 --------------------------------------------------------
166 purpose -- if the row indices of the front matrix are in
167 different order than the row indices of L_{bnd{J},J},
168 sort the rows of L_{bnd{J},J} into ascending order
169 w.r.t the row indices of the front matrix.
170
171 created -- 98mar05, cca
172 --------------------------------------------------------
173 */
174 void
FrontMtx_permuteLowerMatrices(FrontMtx * frontmtx,int msglvl,FILE * msgFile)175 FrontMtx_permuteLowerMatrices (
176 FrontMtx *frontmtx,
177 int msglvl,
178 FILE *msgFile
179 ) {
180 SubMtx *mtxLJ ;
181 int ii, jj, J, mustdo, neqns, nfront, nJ, nrowJ, nrowUJ ;
182 int *map, *rowindJ, *rowindUJ ;
183 /*
184 ---------------
185 check the input
186 ---------------
187 */
188 if ( frontmtx == NULL || (msglvl > 0 && msgFile == NULL) ) {
189 fprintf(stderr,
190 "\n fatal error in FrontMtx_permuteLowerMatrices(%p,%d,%p)"
191 "\n badn input\n", frontmtx, msglvl, msgFile) ;
192 exit(-1) ;
193 }
194 nfront = FrontMtx_nfront(frontmtx) ;
195 neqns = FrontMtx_neqns(frontmtx) ;
196 map = IVinit(neqns, -1) ;
197 for ( J = 0 ; J < nfront ; J++ ) {
198 mtxLJ = FrontMtx_lowerMtx(frontmtx, nfront, J) ;
199 if ( mtxLJ != NULL ) {
200 nJ = FrontMtx_frontSize(frontmtx, J) ;
201 FrontMtx_rowIndices(frontmtx, J, &nrowJ, &rowindJ) ;
202 SubMtx_rowIndices(mtxLJ, &nrowUJ, &rowindUJ) ;
203 for ( ii = nJ, jj = mustdo = 0 ; ii < nrowJ ; ii++, jj++ ) {
204 if ( rowindJ[ii] != rowindUJ[jj] ) {
205 mustdo = 1 ; break ;
206 }
207 }
208 if ( mustdo == 1 ) {
209 for ( ii = 0 ; ii < nrowJ ; ii++ ) {
210 map[rowindJ[ii]] = ii ;
211 }
212 for ( ii = 0 ; ii < nrowUJ ; ii++ ) {
213 rowindUJ[ii] = map[rowindUJ[ii]] ;
214 }
215 SubMtx_sortRowsUp(mtxLJ) ;
216 for ( ii = 0 ; ii < nrowUJ ; ii++ ) {
217 rowindUJ[ii] = rowindJ[rowindUJ[ii]] ;
218 }
219 }
220 }
221 }
222 IVfree(map) ;
223
224 return ; }
225
226 /*--------------------------------------------------------------------*/
227 /*
228 --------------------------------------------------
229 purpose -- to reorder the column indices in bnd{J}
230 to be ascending order w.r.t. K cup bnd{K}
231
232 created -- 98mar07, cca
233 --------------------------------------------------
234 */
235 static void
FrontMtx_reorderColumnIndices(FrontMtx * frontmtx,int J,int K,int map[],int msglvl,FILE * msgFile)236 FrontMtx_reorderColumnIndices (
237 FrontMtx *frontmtx,
238 int J,
239 int K,
240 int map[],
241 int msglvl,
242 FILE *msgFile
243 ) {
244 int ii, ncolJ, ncolK, nJ ;
245 int *colindJ, *colindK ;
246
247 if ( msglvl > 2 ) {
248 fprintf(msgFile, "\n\n inside reorderColumnIndices(%d,%d)", J, K) ;
249 fflush(msgFile) ;
250 }
251 nJ = FrontMtx_frontSize(frontmtx, J) ;
252 FrontMtx_columnIndices(frontmtx, J, &ncolJ, &colindJ) ;
253 if ( msglvl > 2 ) {
254 fprintf(msgFile, "\n nJ = %d, ncolJ = %d", nJ, ncolJ) ;
255 fflush(msgFile) ;
256 }
257 if ( ncolJ == 0 ) {
258 return ;
259 }
260 FrontMtx_columnIndices(frontmtx, K, &ncolK, &colindK) ;
261 if ( msglvl > 2 ) {
262 fprintf(msgFile, ", ncolK = %d", ncolK) ;
263 fflush(msgFile) ;
264 }
265 if ( ncolK == 0 ) {
266 fprintf(stderr, "\n fatal error FrontMtx_reorderColumnIndices()"
267 "\n J = %d, K = %d, nJ = %d, ncolJ = %d, ncolK = %d\n",
268 J, K, nJ, ncolJ, ncolK) ;
269 exit(-1) ;
270 }
271 if ( msglvl > 2 ) {
272 fprintf(msgFile, "\n colindJ") ;
273 IVfprintf(msgFile, ncolJ, colindJ) ;
274 fprintf(msgFile, "\n colindK") ;
275 IVfprintf(msgFile, ncolK, colindK) ;
276 fflush(msgFile) ;
277 }
278 for ( ii = 0 ; ii < ncolK ; ii++ ) {
279 map[colindK[ii]] = ii ;
280 }
281 for ( ii = nJ ; ii < ncolJ ; ii++ ) {
282 colindJ[ii] = map[colindJ[ii]] ;
283 }
284 if ( msglvl > 2 ) {
285 fprintf(msgFile, "\n local colindJ") ;
286 IVfprintf(msgFile, ncolJ, colindJ) ;
287 fflush(msgFile) ;
288 }
289 IVqsortUp(ncolJ - nJ, colindJ + nJ) ;
290 for ( ii = nJ ; ii < ncolJ ; ii++ ) {
291 colindJ[ii] = colindK[colindJ[ii]] ;
292 }
293 if ( msglvl > 2 ) {
294 fprintf(msgFile, "\n global colindJ") ;
295 IVfprintf(msgFile, ncolJ, colindJ) ;
296 fflush(msgFile) ;
297 }
298 return ; }
299
300 /*--------------------------------------------------------------------*/
301 /*
302 -----------------------------------------------
303 purpose -- to reorder the row indices in bnd{J}
304 to be ascending order w.r.t. K cup bnd{K}
305
306 created -- 98mar07, cca
307 -----------------------------------------------
308 */
309 static void
FrontMtx_reorderRowIndices(FrontMtx * frontmtx,int J,int K,int map[],int msglvl,FILE * msgFile)310 FrontMtx_reorderRowIndices (
311 FrontMtx *frontmtx,
312 int J,
313 int K,
314 int map[],
315 int msglvl,
316 FILE *msgFile
317 ) {
318 int ii, nrowJ, nrowK, nJ ;
319 int *rowindJ, *rowindK ;
320
321 if ( msglvl > 2 ) {
322 fprintf(msgFile, "\n\n inside reorderRowIndices(%d,%d)", J, K) ;
323 fflush(msgFile) ;
324 }
325 nJ = FrontMtx_frontSize(frontmtx, J) ;
326 FrontMtx_rowIndices(frontmtx, J, &nrowJ, &rowindJ) ;
327 if ( msglvl > 2 ) {
328 fprintf(msgFile, "\n nJ = %d, nrowJ = %d", nJ, nrowJ) ;
329 fflush(msgFile) ;
330 }
331 if ( nrowJ == 0 ) {
332 return ;
333 }
334 FrontMtx_rowIndices(frontmtx, K, &nrowK, &rowindK) ;
335 if ( msglvl > 2 ) {
336 fprintf(msgFile, ", nrowK = %d", nrowK) ;
337 fflush(msgFile) ;
338 }
339 if ( nrowK == 0 ) {
340 fprintf(stderr, "\n fatal error FrontMtx_reorderRowIndices()"
341 "\n J = %d, K = %d, nJ = %d, nrowJ = %d, nrowK = %d\n",
342 J, K, nJ, nrowJ, nrowK) ;
343 exit(-1) ;
344 }
345 if ( msglvl > 2 ) {
346 fprintf(msgFile, "\n rowindJ") ;
347 IVfprintf(msgFile, nrowJ, rowindJ) ;
348 fprintf(msgFile, "\n rowindK") ;
349 IVfprintf(msgFile, nrowK, rowindK) ;
350 fflush(msgFile) ;
351 }
352 for ( ii = 0 ; ii < nrowK ; ii++ ) {
353 map[rowindK[ii]] = ii ;
354 }
355 for ( ii = nJ ; ii < nrowJ ; ii++ ) {
356 rowindJ[ii] = map[rowindJ[ii]] ;
357 }
358 if ( msglvl > 2 ) {
359 fprintf(msgFile, "\n local rowindJ") ;
360 IVfprintf(msgFile, nrowJ, rowindJ) ;
361 fflush(msgFile) ;
362 }
363 IVqsortUp(nrowJ - nJ, rowindJ + nJ) ;
364 for ( ii = nJ ; ii < nrowJ ; ii++ ) {
365 rowindJ[ii] = rowindK[rowindJ[ii]] ;
366 }
367 if ( msglvl > 2 ) {
368 fprintf(msgFile, "\n global rowindJ") ;
369 IVfprintf(msgFile, nrowJ, rowindJ) ;
370 fflush(msgFile) ;
371 }
372 return ; }
373
374 /*--------------------------------------------------------------------*/
375