Debian Codegraph @

3rdparty/dissection/src/Algebra/SparseRenumbering.cpp

raw
1 /*! \file SparseRenumbering.cpp
2 \brief tridiagonal factorization algorithm with Cuthill-McKee
3 \author François-Xavier Roux, ONERA, Laboratoire Jacques-Louis Lions
4 \author Atsushi Suzuki, Laboratoire Jacques-Louis Lions
5 \date Jul. 12th 2015
6 \date Nov. 30th 2016
7 */
8
9 // This file is part of Dissection
10 //
11 // Dissection is free software: you can redistribute it and/or modify
12 // it under the terms of the GNU General Public License as published by
13 // the Free Software Foundation, either version 3 of the License, or
14 // (at your option) any later version.
15 //
16 // Linking Dissection statically or dynamically with other modules is making
17 // a combined work based on Disssection. Thus, the terms and conditions of
18 // the GNU General Public License cover the whole combination.
19 //
20 // As a special exception, the copyright holders of Dissection give you
21 // permission to combine Dissection program with free software programs or
22 // libraries that are released under the GNU LGPL and with independent modules
23 // that communicate with Dissection solely through the Dissection-fortran
24 // interface. You may copy and distribute such a system following the terms of
25 // the GNU GPL for Dissection and the licenses of the other code concerned,
26 // provided that you include the source code of that other code when and as
27 // the GNU GPL requires distribution of source code and provided that you do
28 // not modify the Dissection-fortran interface.
29 //
30 // Note that people who make modified versions of Dissection are not obligated
31 // to grant this special exception for their modified versions; it is their
32 // choice whether to do so. The GNU General Public License gives permission to
33 // release a modified version without this exception; this exception also makes
34 // it possible to release a modified version which carries forward this
35 // exception. If you modify the Dissection-fortran interface, this exception
36 // does not apply to your modified version of Dissection, and you must remove
37 // this exception when you distribute your modified version.
38 //
39 // This exception is an additional permission under section 7 of the GNU
40 // General Public License, version 3 ("GPLv3")
41 //
42 // Dissection is distributed in the hope that it will be useful,
43 // but WITHOUT ANY WARRANTY; without even the implied warranty of
44 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
45 // GNU General Public License for more details.
46 //
47 // You should have received a copy of the GNU General Public License
48 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
49 //
50
51 #include <cstdio>
52 #include <cstdlib>
53 #include <list>
54 #include <algorithm>
55 #include "Algebra/SparseRenumbering.hpp"
56 #include "Driver/DissectionDefault.hpp"
57 #include "Compiler/arithmetic.hpp"
58 #include "Compiler/DissectionIO.hpp"
59
60 using std::list;
61
62 void CMK_number(const int dim, const int *ptrows, const int *indcols,
63 vector<int> &new2old, const bool verbose, FILE *fp)
64 {
65 vector<int> list, indic, connect;
66 vector<bool> mask;
67 int i1_prev, i2_prev, i0, i1;
68 double profile, min_profile;
69
70 connect.resize(dim);
71 list.resize(dim);
72 indic.resize(dim);
73 mask.resize(dim);
74
75 // compute initial profile
76 i1_prev = 0;
77 i2_prev = indcols[ptrows[0]];
78 for (int k = (ptrows[0] + 1); k < ptrows[1]; k++) {
79 i2_prev = indcols[k] > i2_prev ? indcols[k] : i2_prev;
80 }
81 min_profile = ((double)(i2_prev - i1_prev + 2)
82 * (double)(i2_prev - i1_prev + 1)) * 0.5;
83 while (i2_prev < (dim - 1)) {
84 int i1 = i2_prev + 1;
85 int i2 = indcols[ptrows[i1_prev]];
86 for (int k = (ptrows[i1_prev] + 1); k < ptrows[i2_prev + 1]; k++) {
87 i2 = indcols[k] > i2 ? indcols[k] : i2;
88 }
89 min_profile += (double)(i2 - i1 + 2) * (double)(i2 - i1 + 1) * 0.5;
90 i1_prev = i1;
91 i2_prev = i2;
92 }
93 diss_printf(verbose, fp,
94 "%s %d : Cuthill McKee renumbering : init block : %g :: ",
95 __FILE__, __LINE__, min_profile);
96
97 // initialize frontal renumbering from an excentric point
98 for (int i = 0; i < dim; i++) {
99 connect[i] = ptrows[i + 1] - ptrows[i];
100 mask[i] = false;
101 }
102 i0 = 0; // initialization : critical when connent[] == dim
103 {
104 int imin = dim; // find index that attains minimun of connect[]
105 for (int i = 0; i < dim; i++) {
106 if (imin > connect[i]) {
107 imin = connect[i];
108 i0 = i;
109 }
110 }
111 }
112 mask[i0] = true;
113 profile = frontal_numb(dim, ptrows, indcols, i0, list, indic, connect);
114 i1 = list[dim - 1];
115
116 diss_printf(verbose, fp, "- > node %d : %g :: ", i0, profile);
117 if (profile < min_profile) {
118 min_profile = profile;
119 }
120 else {
121 for (int i = 0; i < dim; i++) {
122 list[i] = i;
123 }
124 }
125 profile = min_profile;
126 min_profile = min_profile + 1.0;
127
128 // repeat frontal numbering as long as profile improves
129 while (profile < min_profile) {
130 min_profile = profile;
131 for (int i = 0; i < dim; i++) {
132 new2old[i] = list[i];
133 }
134 for (int i = 0; i < dim; i++) {
135 connect[i] = ptrows[i + 1] - ptrows[i];
136 }
137 {
138 i0 = 0; // initialization : critical when connent[] == dim
139 int imin = dim;
140 for (int k = ptrows[i1]; k < ptrows[i1 + 1]; k++) {
141 const int ii = indcols[k];
142 if (imin > connect[ii]) {
143 imin = connect[ii];
144 i0 = ii;
145 }
146 }
147 if (mask[i0]) {
148 for (int i = (dim - 1); i >=0; i--) {
149 if (!mask[list[i]]) {
150 i0 = list[i];
151 break;
152 }
153 }
154 }
155 }
156 mask[i0] = true;
157 profile = frontal_numb(dim, ptrows, indcols, i0, list, indic, connect);
158 i1 = list[dim - 1];
159 diss_printf(verbose, fp, "- > node: %d : %g :: ", i0, profile);
160 } // while
161
162 diss_printf(verbose, fp, "-> optimazied : %g\n", min_profile);
163 }
164
165 double frontal_numb(const int dim, const int *ptrows, const int *indcols,
166 const int i0,
167 vector<int> &list,
168 vector<int> &indic, vector<int> &connect)
169 {
170 int n, nn, i1, i2, i1_prev, i2_prev, k1, k2;
171 double profile;
172 // compute nodal connectivity degree
173 for (int i = 0; i < dim; i++) {
174 connect[i] = ptrows[i + 1] - ptrows[i];
175 }
176 #if 1
177 for (int i = 0; i < dim; i++) {
178 indic[i] = 0;
179 }
180 n = 0;
181 nn = (-1);
182 list[0] = i0;
183 indic[i0] = 1;
184 while (n < (dim - 1)) {
185 nn++;
186 int j = list[nn];
187 // renumber un-numbered neigbours of j, in increasing connectivity order
188 int k = 0;
189 for (int l = ptrows[j]; l < ptrows[j + 1]; l++) {
190 const int i = indcols[l];
191 if (indic[i] == 0) {
192 int ki = 1;
193 for ( ; ki <= k; ki++) {
194 if (connect[i] < connect[list[n + ki]]) {
195 break;
196 }
197 }
198 k++;
199 for (int kk = k; kk >= (ki + 1); kk--) {
200 list[n + kk] = list[n + kk - 1];
201 }
202 list[n + ki] = i;
203 } // if (indic[i] == 0)
204 } // update connectivity degree of un-numbered nodes
205 for (int kk = (n + 1); kk <= (n + k); kk++) {
206 const int ii = list[kk];
207 for (int m = ptrows[ii]; m < ptrows[ii + 1]; m++) {
208 connect[indcols[m]]--;
209 }
210 }
211 for (int kk = (n + 1); kk <= (n + k); kk++) {
212 indic[list[kk]] = 1;
213 }
214 n += k;
215 } // while (n < (dim - 1))
216 // build old to new correspondance
217 for (int i = 0; i < dim; i++) {
218 indic[list[i]] = i;
219 }
220 #else
221 std::list<int> idexlist;
222 vector<bool> mask;
223 mask.resize(dim, false);
224 idexlist.push_back(i0);
225 std::list<int>::iterator it = idexlist.begin();
226 mask[(*it)] = true;
227 n = 0;
228 std::list<int>::iterator nt = idexlist.begin();
229 while (n < (dim - 1)) {
230 int k = 0;
231 for (int l = ptrows[(*it)]; l < ptrows[(*it) + 1]; l++) {
232 const int ii = indcols[l];
233 if (!mask[ii]) {
234 bool flag = false;
235 std::list<int>::iterator kt = nt;
236 ++kt;
237 for (int kk = 0 ; kk < k; kk++, ++kt) {
238 if (connect[ii] < connect[(*kt)]) {
239 idexlist.insert(kt, ii);
240 flag = true;
241 break;
242 }
243 }
244 if (!flag) {
245 idexlist.push_back(ii);
246 }
247 k++;
248 }
249 }
250 ++it;
251 std::list<int>::iterator kt = nt;
252 int kk = 0;
253 for ( ; kk < k; ++kt, kk++) {
254 for (int m = ptrows[(*kt)]; m < ptrows[(*kt) + 1]; m++) {
255 connect[indcols[m]]--;
256 }
257 mask[(*kt)] = true;
258 ++nt;
259 }
260 n += k;
261 }
262 {
263 int i = 0;
264 std::list<int>::iterator it = idexlist.begin();
265 for (; it != idexlist.end(); ++it, i++) {
266 list[i] = (*it);
267 indic[(*it)] = i;
268 }
269 }
270 idexlist.clear();
271 #endif
272
273 // compute profile
274 i1_prev = 0;
275 k1 = ptrows[list[i1_prev]];
276 k2 = ptrows[list[i1_prev] + 1];
277 i2_prev = indic[indcols[k1]];
278 for (int k = (k1 + 1); k < k2; k++) {
279 i2_prev = indic[indcols[k]] > i2_prev ? indic[indcols[k]] : i2_prev;
280 }
281 profile = ((double)(i2_prev - i1_prev + 1) *
282 (double)(i2_prev - i1_prev + 2) * 0.5);
283 while (i2_prev < (dim - 1)) {
284 i1 = i2_prev + 1;
285 i2 = i1;
286 for (int i = i1_prev; i <= i2_prev; i++) {
287 k1 = ptrows[list[i]];
288 k2 = ptrows[list[i] + 1];
289 i2 = std::max<int>((int)i2, (int)indic[indcols[k1]]);
290 for (int k = (k1 + 1); k < k2; k++) {
291 i2 = indic[indcols[k]] > i2 ? indic[indcols[k]] : i2;
292 }
293 }
294 profile += ((double)(i2 - i1 + 1) * (double)(i2 - i1 + 2) * 0.5);
295 i1_prev = i1;
296 i2_prev = i2;
297 }
298 return profile;
299 }
300
301 int point_front(const int dim, const int *ptrows, const int *indcols,
302 vector<int> &new2old, vector<int> &p_front, const bool verbose,
303 FILE *fp)
304 {
305 int nfront, ilast;
306 vector<int> old2new, p_front1;
307 vector<bool> mask;
308 const int size_thrs = 24;
309 old2new.resize(dim);
310 for (int i = 0; i < dim; i++) {
311 old2new[new2old[i]] = i;
312 }
313 p_front.resize(dim + 1); // for safty
314
315 nfront = 0;
316 p_front[0] = 0;
317 ilast = (-1);
318 while (ilast < (dim - 1)) { // loop ilast
319 ilast++;
320 bool flag_cont = false;
321 bool flag_break = false;
322 const int ii = new2old[ilast];
323 nfront++;
324 int isup = (-1);
325 for (int k = ptrows[ii]; k < ptrows[ii + 1]; k++) {
326 const int jj = old2new[indcols[k]];
327 isup = jj > isup ? jj : isup;
328 }
329 p_front[nfront] = isup + 1;
330 while (isup > ilast) {
331 ilast = isup;
332 for (int i = p_front[nfront - 1]; i < p_front[nfront]; i++) {
333 const int ii = new2old[i];
334 for (int k = ptrows[ii]; k < ptrows[ii + 1]; k++) {
335 const int jj = old2new[indcols[k]];
336 isup = jj > isup ? jj : isup;
337 }
338 } // loop : i
339 if (isup == ilast) {
340 flag_cont = true;
341 break; // continue loop_ilast
342 }
343 nfront++;
344 p_front[nfront] = isup + 1;
345 if (isup == (dim - 1)) {
346 flag_break = true;
347 break; // exit loop_ilast
348 }
349 }
350 if (flag_cont) {
351 continue;
352 }
353 if (flag_break) {
354 break;
355 }
356 } // loop ilast
357 old2new.clear();
358 mask.resize(nfront + 1);
359 p_front1.resize(nfront + 1);
360 for (int k = 0; k < nfront; k++) {
361 const int itmp = p_front[k + 1] - p_front[k];
362 if (itmp >= size_thrs) {
363 mask[k] = true;
364 }
365 else {
366 mask[k] = false;
367 }
368 }
369 mask[nfront] = true;
370 int n = 0;
371 {
372 int k = 0;
373 p_front1[0] = p_front[0];
374 int k0 = k;
375 while (k < nfront) {
376 int flag = 0;
377 if (!mask[k0]) {
378 if (!mask[k + 1]) {
379 if ((p_front[k + 1] - p_front[k0]) < size_thrs) {
380 flag = 2;
381 }
382 else {
383 flag = (-2);
384 }
385 }
386 else {
387 if ((k == 0) && mask[1]) {
388 flag = 2;
389 }
390 else {
391 if ((k0 == k) || (k == (nfront - 1))) {
392 flag = 0;
393 }
394 else {
395 flag = (-1);
396 }
397 }
398 } // if (!mask[k + 1])
399 } // if (!mask[k0])
400 else {
401 if (k == (nfront - 2) && !mask[nfront - 1]) {
402 flag = 1;
403 }
404 }
405 switch (flag) {
406 case 1:
407 p_front1[n + 1] = p_front[k + 2];
408 n++;
409 k += 2;
410 k0 = k;
411 break;
412 case (-2):
413 p_front1[n + 1] = p_front[k];
414 n++;
415 k0 = k;
416 break;
417 case (-1):
418 p_front1[n + 1] = p_front[k];
419 p_front1[n + 2] = p_front[k + 1];
420 n += 2;
421 k++;
422 k0 = k;
423 break;
424 case (0):
425 p_front1[n + 1] = p_front[k + 1];
426 n++;
427 k++;
428 k0 = k;
429 break;
430 case 2:
431 k++;
432 break;
433 }
434 } // while (k < nfront)
435 } // scope for k, n etc.
436 if ((p_front1[0] != 0)|| (p_front1[n] != p_front[nfront])) {
437 diss_printf(verbose, fp, "%s %d : error %d -> %d\n", __FILE__, __LINE__,
438 p_front[nfront], p_front1[n]);
439 exit(-1);
440 }
441 nfront = n;
442 p_front.resize(nfront + 1);
443 for (int k = 0; k <= n; k++) {
444 p_front[k] = p_front1[k];
445 }
446 return nfront;
447 }
448
449 int getColorMaskCSR(int *color_mask, const CSR_indirect *csr,
450 const bool verbose, FILE *fp)
451 {
452 const int dim = csr->n;
453 int *prow = csr->ptRows;
454 int *indcols = csr->indCols;
455
456 for (int i = 0; i < dim; i++) {
457 color_mask[i] = (-1);
458 }
459
460 list<int> graph_start;
461 int num_isolated = 0;
462 for (int i = 0 ; i < dim; i++) {
463 if ((prow[i] + 1) == prow[i + 1]) {
464 num_isolated++;
465 color_mask[i] = 0;
466 }
467 }
468 if (num_isolated > 0) {
469 diss_printf(verbose, fp,
470 "%s %d : isolated = %d\n", __FILE__, __LINE__, num_isolated);
471 }
472 int color = 0;
473 for (int i = 0; i < dim; i++) {
474 if (color_mask[i] == (-1)) {
475 color++;
476 color_mask[i] = color;
477 graph_start.clear();
478 graph_start.push_back(i);
479 for (list<int>::iterator it = graph_start.begin();
480 it != graph_start.end(); ++it) {
481 for (int k = prow[(*it)]; k < prow[(*it) + 1]; k++) {
482 if (color_mask[indcols[k]] == (-1)) {
483 color_mask[indcols[k]] = color;
484 graph_start.push_back(indcols[k]);
485 }
486 }
487 } // loop : it
488 }
489 } // loop : i
490 // post process merge color with small size into previous color
491 int reduced = 0;
492 diss_printf(verbose, fp, "%s %d : before color = %d\n",
493 __FILE__, __LINE__, color);
494 int m = 1;
495 while (m <= color) {
496 int count = 0;
497 for (int i = 0; i < dim; i++) {
498 if (color_mask[i] == m) {
499 count++;
500 }
501 }
502 if ((count <= DIM_AUG_KERN) && (color > 1)){ // to treat very small matrix
503 reduced++;
504 color--;
505 for (int i = 0; i < dim; i++) {
506 if (color_mask[i] == m) {
507 color_mask[i] = (-1);
508 }
509 else if (color_mask[i] > m) {
510 color_mask[i]--;
511 }
512 }
513 }
514 else {
515 m++;
516 }
517 }
518 diss_printf(verbose, fp, "%s %d : after fused = %d color = %d\n",
519 __FILE__, __LINE__, reduced, color);
520 return color;
521 }
522