Debian Codegraph @

3rdparty/dissection/src/Splitters/BisectionTree.cpp

raw
1 /*! \file BisectionTree.cpp
2 \brief ordeing by graph decomposer, SCOTCH or METIS
3 \author Xavier Juvigny, ONERA
4 \date Jul. 2nd 2012
5 \date Nov. 30th 2016
6 */
7
8 // This file is part of Dissection
9 //
10 // Dissection is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // Linking Dissection statically or dynamically with other modules is making
16 // a combined work based on Disssection. Thus, the terms and conditions of
17 // the GNU General Public License cover the whole combination.
18 //
19 // As a special exception, the copyright holders of Dissection give you
20 // permission to combine Dissection program with free software programs or
21 // libraries that are released under the GNU LGPL and with independent modules
22 // that communicate with Dissection solely through the Dissection-fortran
23 // interface. You may copy and distribute such a system following the terms of
24 // the GNU GPL for Dissection and the licenses of the other code concerned,
25 // provided that you include the source code of that other code when and as
26 // the GNU GPL requires distribution of source code and provided that you do
27 // not modify the Dissection-fortran interface.
28 //
29 // Note that people who make modified versions of Dissection are not obligated
30 // to grant this special exception for their modified versions; it is their
31 // choice whether to do so. The GNU General Public License gives permission to
32 // release a modified version without this exception; this exception also makes
33 // it possible to release a modified version which carries forward this
34 // exception. If you modify the Dissection-fortran interface, this exception
35 // does not apply to your modified version of Dissection, and you must remove
36 // this exception when you distribute your modified version.
37 //
38 // This exception is an additional permission under section 7 of the GNU
39 // General Public License, version 3 ("GPLv3")
40 //
41 // Dissection is distributed in the hope that it will be useful,
42 // but WITHOUT ANY WARRANTY; without even the implied warranty of
43 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44 // GNU General Public License for more details.
45 //
46 // You should have received a copy of the GNU General Public License
47 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
48 //
49
50 // ==============================================================
51 // == Bisection tree : Implementation of some methods ==
52 // ==============================================================
53 # include <cstdlib>
54 # include <cstring>
55 # include <stdexcept>
56 # include <algorithm>
57 # include <map>
58 # include <time.h>
59 # include "Splitters/BisectionTree.hpp"
60 # include "Splitters/ScotchSplitter.hpp"
61 # include "Splitters/MetisSplitter.hpp"
62 # include "Splitters/BitManipulations.hpp"
63 # include "Compiler/DebugUtils.hpp"
64 # include "Compiler/arithmetic.hpp"
65 # include "Compiler/DissectionIO.hpp"
66
67 #include <vector>
68 #include <list>
69
70 using namespace Dissection;
71 using std::vector;
72 using std::list;
73
74 unsigned*
75 Tree::compLoc2Dom(unsigned dim) const
76 {
77 /** The splitters sort the domains to be compatible
78 with the domain numerotation cared in this
79 class...
80 */
81 unsigned nbDoms = (1<<_nbLevels) - 1;
82 unsigned* loc2Dom = new unsigned[dim];
83 for (unsigned iDom = 0; iDom < nbDoms; iDom++)
84 {
85 for (unsigned iNode = _ptOnDomains[iDom];
86 iNode<_ptOnDomains[iDom]+_sizeOfDomains[iDom];
87 iNode++) {
88 assert(iNode<dim);
89 loc2Dom[iNode] = iDom+1;
90 }
91 }
92 return loc2Dom;
93 }
94 // ==============================================================
95 void
96 Tree::renumberingInterface(unsigned nperm, unsigned* perm,
97 const SetOfStrips& paral,
98 const SetOfStrips& parar,
99 const SetOfStrips& seq,
100 unsigned layer, unsigned iDom ) const
101 {
102 if (nperm<3) return;
103 long endPerm = long(nperm-1);
104 unsigned endParal= 0;
105 unsigned endParar= 0;
106 unsigned endSeq = 0;
107 // Begin sorting perm indices which are in paral :
108 if (paral.numberOfStrips() > 0) {
109 unsigned iperm = 0;
110 while (long(iperm) <= endPerm) {
111 if (paral.contains(perm[iperm]))
112 iperm++;
113 else {
114 std::swap(perm[iperm],perm[endPerm]);
115 endPerm -= 1;
116 }
117 }
118 endParal = iperm;
119 if (endParal > 1)
120 std::sort(perm,perm+endParal);
121 }
122 else endParal = 0;
123 // Sorting sequential indices given
124 if (seq.numberOfStrips() > 0) {
125 unsigned iperm = endParal;
126 endPerm = nperm-1;
127 while ((long)iperm <= endPerm) {
128 if (seq.contains(perm[iperm]))
129 ++iperm;
130 else {
131 std::swap(perm[iperm],perm[endPerm]);
132 --endPerm;
133 }
134 }
135 endSeq = iperm;
136 if (endSeq-endParal > 1)
137 std::sort(perm+endParal,perm+endSeq);
138 }
139 else endSeq = endParal;
140 // Sorting parallel indices from right interface :
141 if (parar.numberOfStrips() > 0) {
142 unsigned iperm = endSeq;
143 endPerm = nperm-1;
144 while (long(iperm) <= endPerm) {
145 if (parar.contains(perm[iperm]))
146 iperm++;
147 else {
148 std::swap(perm[iperm],perm[endPerm]);
149 endPerm -= 1;
150 }
151 }
152 endParar = iperm;
153 if (endParar-endSeq > 1)
154 std::sort(perm+endSeq,perm+endParar);
155 }
156 else endParar = endSeq;
157 if (endParar < nperm-1)
158 std::sort(perm+endParar,perm+nperm);
159
160 // Recursive calling :
161 if (nodeLayer(iDom) < _nbLevels-2) {
162 SetOfStrips paral2, parar2, seq2;
163 iDom *= 2;
164 unsigned leftChild = (iDom<<1);
165 unsigned rghtChild = leftChild+1;
166 SetOfStrips& lStrip = _interco[leftChild-1][layer];
167 SetOfStrips& rStrip = _interco[rghtChild-1][layer];
168 lStrip.para_union(rStrip, paral2, parar2,seq2);
169 if (endParal > 0) {
170 renumberingInterface(endParal, perm, paral2, parar2,
171 seq2, layer, iDom );
172 }
173 // For sequential part, given priority to the left
174 // interface if right interface has parallel indices
175 if (endParar > endSeq) {
176 renumberingInterface(endSeq-endParal, perm+endParal,
177 paral2, parar2, seq2, layer, iDom );
178 iDom += 1;
179 unsigned leftChild = (iDom<<1);
180 unsigned rghtChild = leftChild+1;
181 SetOfStrips& lStrip = _interco[leftChild-1][layer];
182 SetOfStrips& rStrip = _interco[rghtChild-1][layer];
183 lStrip.para_union(rStrip, paral2, parar2,seq2);
184 renumberingInterface(endParar-endSeq, perm+endSeq,
185 paral2, parar2, seq2, layer, iDom );
186 } else {
187 iDom += 1;
188 unsigned leftChild = (iDom<<1);
189 unsigned rghtChild = leftChild+1;
190 SetOfStrips& lStrip = _interco[leftChild-1][layer];
191 SetOfStrips& rStrip = _interco[rghtChild-1][layer];
192 lStrip.para_union(rStrip, paral2, parar2,seq2);
193 renumberingInterface(endSeq-endParal, perm+endParal,
194 paral2, parar2, seq2, layer, iDom );
195 }
196 }
197 }
198 // ==============================================================
199 Tree::Tree(FILE *fp,
200 bool &berr, unsigned dim,
201 const CSR_indirect *csr,
202 const bool isSym, //const bool isLower,
203 const int *remap_eqn, //const int* map_indcols,
204 unsigned nbMaxLevel, unsigned minSize,
205 splitter spltFct,
206 bool checkData, const bool verbose) :
207 _verbose(verbose), _glob2dom(NULL), _isSym(isSym)
208 {
209 const int *ptRows = csr->ptRows;
210 const int *indCols = csr->indCols;
211 const int *indVals = csr->indVals;
212 const int *unsym_upper2lower = csr->indVals_unsym;
213 bool ok;
214 if (!spltFct) spltFct = &ScotchSplitter;
215 // 0. Remove loops for diagonal elements (Metis and Scotch
216 // don't like loops into graph)
217 int * ptRows2, * indCols2;
218 int *indCols_sbdmn, *indCols_idxStrip, *indCols_idxSbdmn;
219 unsigned *l2d;
220
221 removeLoops(dim, ptRows, indCols, ptRows2, indCols2);
222 _local2global = new int[dim];
223 _global2local = new int[dim];
224 int nbDoms;
225
226 ok = (*spltFct)(dim, ptRows2,indCols2,nbMaxLevel,minSize,
227 _global2local,_local2global,
228 nbDoms,_ptOnDomains,_sizeOfDomains,
229 checkData, verbose, fp);
230 _nbLevels = nbMaxLevel;
231 assert(nbDoms == (1<<_nbLevels)-1);
232
233 l2d = compLoc2Dom(dim);
234
235 # if defined(DISSECTION_DEBUG)
236 for (unsigned ii = 0; ii < dim; ii++)
237 assert(_global2local[_local2global[ii]] == ii);
238 // Save profile of the skeleton of the matrix with new ordering
239 // into a file.
240 fich = fopen("matrixProfile.dat", "w");
241 fprintf(fich,"%d\n",dim);
242 int nz = 0;
243 fprintf(fich,"%d ",nz);
244 for (int iLoc = 0; iLoc < dim; iLoc++) {
245 int iGlob = _local2global[iLoc];
246 int nbCol = ptRows[iGlob+1]-ptRows[iGlob];
247 nz += nbCol;
248 fprintf(fich,"%d ",nz);
249 }
250 CHECK(nz == ptRows[dim], "Wrong number of non zero coefficients?");
251 fprintf(fich,"\n");
252 for (int iLoc = 0; iLoc < dim; iLoc++) {
253 int iGlob = _local2global[iLoc];
254 for (int jCol = ptRows[iGlob]; jCol<ptRows[iGlob+1];jCol++)
255 {
256 int jGlob = indCols[jCol];
257 int jLoc = _global2local[jGlob];
258 fprintf(fich,"%d ",jLoc);
259 }
260 }
261 fprintf(fich,"\n");
262 fclose(fich);
263 // l2d keeps the index of subdomain where node is included
264 // ptDom keeps begining address of subdomain with sorting : nb_sbdm ... 1
265 // l2d = compLoc2Dom(dim);
266 unsigned* ptDom = new unsigned[(1<<_nbLevels)-1];
267 fich = fopen("sparseMatrix3.dat", "w");
268 fprintf(fich,"%d\n",dim);
269 nz = 0;
270 unsigned d = 0;
271 fprintf(fich,"%d ",nz);
272 for (long iLvl = _nbLevels-1; iLvl >=0; iLvl--) {
273 unsigned begDom = (1<<iLvl);
274 unsigned endDom = 2*begDom;
275 for (unsigned iDom = begDom; iDom < endDom; iDom++) {
276 ptDom[iDom-1] = d;
277 d += _sizeOfDomains[iDom-1];
278 for (unsigned iLoc = _ptOnDomains[iDom-1];
279 iLoc < _ptOnDomains[iDom-1]+_sizeOfDomains[iDom-1];
280 iLoc++)
281 {
282 int iGlob = _local2global[iLoc];
283 int nbCol = ptRows[iGlob+1]-ptRows[iGlob];
284 nz += nbCol;
285 fprintf(fich,"%d ",nz);
286 }
287 }
288 }
289 assert(nz == ptRows[dim]);
290 CHECK(nz == ptRows[dim], "Wrong number of non zero coefficients?");
291 fprintf(fich,"\n");
292 for (long iLvl = _nbLevels-1; iLvl >=0; iLvl--) {
293 unsigned begDom = (1<<iLvl);
294 unsigned endDom = 2*begDom;
295 for (unsigned iDom = begDom; iDom < endDom; iDom++) {
296 for (unsigned iLoc = _ptOnDomains[iDom-1];
297 iLoc < _ptOnDomains[iDom-1]+_sizeOfDomains[iDom-1];
298 iLoc++)
299 {
300 int iGlob = _local2global[iLoc];
301 for (int jCol = ptRows[iGlob]; jCol<ptRows[iGlob+1];jCol++) {
302 int jGlob = indCols[jCol];
303 int jLoc1 = _global2local[jGlob];
304 unsigned dl = l2d[jLoc1];
305 int jGlob1 = _local2global[jLoc1];
306 jLoc1 -= _ptOnDomains[dl-1];
307 assert(jLoc1 < _sizeOfDomains[dl-1]);
308 jLoc1 += ptDom[dl-1];
309 assert(jLoc1 < dim);
310 fprintf(fich,"%d ",jLoc1);
311 }
312 }
313 }
314 }
315 fprintf(fich,"\n");
316 fclose(fich);
317 delete [] ptDom;
318 # endif
319 // 2. Compute local indices to domains containing this indice
320 // to speed-up symbolic computation
321 unsigned* loc2dom = compLoc2Dom(dim);
322 // 3. Allocation of lists of connection per levels of ancestors
323 // for each node of the bisection tree
324 // NB : Some optimization to do here. Avoiding uniqueness method
325 // checking for each connected nodes if it's in the
326 // connection list, thanks to a logical array with size
327 // equal to indices ?
328 std::list<unsigned>** connections = new std::list<unsigned>*[nbDoms];
329 assert(connections != NULL);
330 connections[0] = NULL;
331 for (unsigned iDom = 2; iDom <= nbDoms; iDom++) {
332 unsigned layer = nodeLayer(iDom);
333 assert(layer < _nbLevels);
334 assert(layer > 0);
335 connections[iDom-1] = new std::list<unsigned>[layer];
336 // a. Filling interconnection between iDom and his ancestors
337 //
338 // i. For each node in iDom :
339 for (unsigned idxVert = _ptOnDomains[iDom-1];
340 idxVert<_ptOnDomains[iDom-1]+_sizeOfDomains[iDom-1]; idxVert++)
341 {
342 unsigned indGlob = _local2global[idxVert];
343 // ii. For global indice node indGlob, search connected
344 // nodes from the matrix skeleton :
345 for (unsigned ptRow = ptRows[indGlob]; ptRow < ptRows[indGlob+1];
346 ptRow++)
347 {
348 unsigned connectGlobInd = indCols[ptRow];
349 unsigned connectLocInd = _global2local[connectGlobInd];
350 unsigned ancestor = loc2dom[connectLocInd];
351 connectLocInd -= _ptOnDomains[ancestor-1];
352
353 if (ancestor < iDom) // If ancestor is an ancestor (and not itself or a child)
354 {
355 unsigned lvlLocDom = nodeLayer(ancestor);
356 connections[iDom-1][lvlLocDom].push_back(connectLocInd);
357 }
358 }// End for (unsigned ptRow
359 }// End for (unsigned idxVert
360 for (unsigned iLayer = 0; iLayer < layer; iLayer++)
361 {
362 connections[iDom-1][iLayer].sort();
363 connections[iDom-1][iLayer].unique();
364 }
365 }// End for (iDom
366 // 4. Convert the nodes connections lists into strips
367 // connections lists
368 assert(connections != NULL);
369 SetOfStrips** stripConnections =
370 new SetOfStrips*[nbDoms];
371 assert(stripConnections != NULL);
372 stripConnections[0] = NULL;
373 for (unsigned iDom = 2; iDom <= nbDoms; iDom++) {
374 unsigned layer = nodeLayer(iDom);
375 assert(layer < _nbLevels);
376 stripConnections[iDom-1] = new SetOfStrips[layer];
377 for (unsigned iLayer = 0; iLayer < layer; iLayer++)
378 {
379 assert(connections != NULL);
380 stripConnections[iDom-1][iLayer]=
381 SetOfStrips(connections[iDom-1][iLayer]);
382 }
383 }
384 // OK, initial connection is decribed as strip
385 // with local indices per domains.
386 // 5. Begin symbolic factorization :
387 _interco = symbolicFactorization(stripConnections);
388 // 6. Renumbering father--children to have one parallel strip
389 // and one sequential strip for interconnection between
390 // children and father.
391 // Renumbering :
392 // Parallel indices from left child | Sequential indices from
393 // left and right children | Parallel indices from right children
394 for (unsigned iDom = 1; iDom < (1<<(_nbLevels-1)); iDom++)
395 {
396 SetOfStrips paral, parar, seq;
397 SetOfStrips::iterator itS;
398 unsigned *perm = new unsigned[sizeOfDomain(iDom)];
399 for (unsigned i = 0; i < sizeOfDomain(iDom); i++)
400 perm[i] = i;
401 unsigned layer = nodeLayer(iDom);
402 assert(layer < _nbLevels-1);
403 unsigned leftChild = (iDom<<1);
404 unsigned rghtChild = leftChild+1;
405 SetOfStrips& lStrip = _interco[leftChild-1][layer];
406 SetOfStrips& rStrip = _interco[rghtChild-1][layer];
407 lStrip.para_union(rStrip, paral, parar,seq);
408 renumberingInterface(sizeOfDomain(iDom), perm, paral, parar,
409 seq, layer, iDom );
410 unsigned* invperm = new unsigned[sizeOfDomain(iDom)];
411 for (unsigned ii = 0; ii < sizeOfDomain(iDom); ii++)
412 invperm[perm[ii]] = ii;
413
414 unsigned curDom = iDom;
415 unsigned nbDoms = 1;
416 for (unsigned iLayer = layer+1; iLayer < _nbLevels; iLayer++)
417 {
418 curDom *= 2;
419 nbDoms *= 2;
420 for (unsigned jDom = curDom; jDom < curDom+nbDoms; jDom++)
421 {
422 // Retrieve connection between jDom and iDom
423 // in old renumbering
424 SetOfStrips& strips = _interco[jDom-1][layer];
425 // and convert into list
426 std::list<unsigned> locConnect = strips;
427 // Convert old renumbering into new renumbering in the list
428 for (std::list<unsigned>::iterator itL = locConnect.begin();
429 itL != locConnect.end(); itL++) {
430 (*itL) = invperm[(*itL)];
431 }
432 locConnect.sort();
433 // Build new strips coming from new renumbering
434 strips = SetOfStrips(locConnect);
435 }// for (jDom
436 }// for (iLayer
437 // Renumbering the local indices for subdomain iDom :
438 // ------------------------------------------------
439 int* tempInd = new int[sizeOfDomain(iDom)];
440 memcpy(tempInd, _local2global+ _ptOnDomains[iDom-1],
441 sizeof(int)*sizeOfDomain(iDom));
442 for (unsigned i = 0; i < sizeOfDomain(iDom); i++) {
443 _local2global[_ptOnDomains[iDom-1]+i] =
444 tempInd[perm[i]];
445 }
446 delete [] tempInd; // 01 Feb.2013 Atsushi
447 delete [] invperm;
448 delete [] perm;
449
450 for (unsigned i = 0; i < sizeOfDomain(iDom); i++) {
451 int l2g = _local2global[_ptOnDomains[iDom-1]+i];
452 _global2local[l2g] = _ptOnDomains[iDom-1]+i;
453 }
454 }// for (iDom
455 // At last, create interconnections between a node set of strips
456 // and his ancestors (out of diagonal and diagonals blocks).
457 // Nb : For layer 0, no ancestors, so...
458 for (unsigned iLayer = 1; iLayer < _nbLevels; iLayer++) {
459 // For each domain contained in layer iLayer :
460 for (unsigned iDom = (1<<iLayer); iDom < (1<<(iLayer+1)); iDom++) {
461 FathersStrips& connection_i = _interco[iDom-1];
462 unsigned jDom = iDom;
463 // For each ancestor of our domain iDom (beginning from the father to root) :
464 for (unsigned jLayer = iLayer; jLayer > 0; jLayer--) {
465 // Compute index of the ancestor in layer jLayer :
466 jDom = jDom/2;
467 FathersStrips& connection_j = _interco[jDom-1];
468 // Retrieve the set of strips describing the direct connection between the
469 // strips
470 for (unsigned kLayer = jLayer; kLayer > 0; kLayer --) {
471 SetOfStrips& stripForRowBlock_jk = connection_i.getRowSetOfStrips(jLayer-1,kLayer-1);
472 SetOfStrips& stripForColBlock_jk = connection_i.getColSetOfStrips(jLayer-1,kLayer-1);
473 // Most of data are copy of out of diagonal strips :
474 stripForRowBlock_jk = connection_i[jLayer-1];
475 stripForColBlock_jk = connection_i[kLayer-1];
476 if (kLayer != jLayer) {// In this case, must change the destination index :
477 SetOfStrips& outOfDiag_strips_jk = connection_j[kLayer-1];
478 SetOfStrips::iterator it_DstBjk = stripForColBlock_jk.begin();
479 for (SetOfStrips::iterator it_Bjk = outOfDiag_strips_jk.begin();
480 it_Bjk != outOfDiag_strips_jk.end(); it_Bjk++) {
481 unsigned decal;
482 while ((it_DstBjk != stripForColBlock_jk.end()) &&
483 (*it_DstBjk).inside(*it_Bjk,decal)) {
484 (*it_DstBjk).begin_dst = (*it_Bjk).begin_src + decal;
485 it_DstBjk ++;
486 }
487 }
488 }
489 }
490 }
491 }
492 }
493 # if defined(DISSECTION_DEBUG)
494 {
495 unsigned iDom;
496 // DEBUGGING : Save filling of the matrix
497 fich = fopen("filledMatrix2.dat", "w");
498 fprintf(fich,"%d\n",_nbLevels);
499 for (iDom = 1; iDom <= nbDoms; iDom++)
500 fprintf(fich,"%d %d\n",_ptOnDomains[iDom - 1],
501 _sizeOfDomains[iDom - 1]);
502 // ancestors connection :
503 // added by Atsush :
504 // iDom ==1 does not have father, hence it is not shown here
505 // strips are shown in order of Idom : {2, 3} {4, 5, 6, 7}
506 // NB : index of _interco[] starts at 0, (iDom - 1) is obligation!!
507 for (unsigned iLevel = 1; iLevel < _nbLevels; iLevel++)
508 {
509 // First domain indice for this level:
510 unsigned begDom = (1<<iLevel);
511 // Last domain indice for this level + 1:
512 unsigned endDom = 2*begDom; // (1 << (iLevel + 1));
513 for (iDom = begDom; iDom < endDom; iDom++) {
514 fprintf(fich,"# iDom = %d\n", iDom);
515 for (unsigned iLayer = 0; iLayer < iLevel; iLayer++) {
516 fprintf(fich,"# iLayer = %d\n", iLayer);
517 fprintf(fich,"%d\t",_interco[iDom-1][iLayer].numberOfStrips());
518 for (SetOfStrips::iterator itS = _interco[iDom-1][iLayer].begin();
519 itS != _interco[iDom-1][iLayer].end(); itS++) {
520 fprintf(fich, "(%d %d) %d\t",
521 (*itS).begin_src, (*itS).begin_dst, (*itS).width);
522 }
523 fprintf(fich,"\n");
524 }// for iLayer
525 }// for iDom
526 }// for iLevel
527 fclose(fich);
528 }
529 #endif
530 // Atsushi : 03 Mar.2012
531 //
532 std::map<int, int>* indCols_bylvl = new std::map<int, int>[_nbLevels];
533
534 int *ptRow_diag = new int[dim];
535 int nnzh = (ptRows[dim] + dim) / 2;
536 int *indVals_tmp = new int [nnzh];
537
538 indCols_sbdmn = new int[ptRows[dim]];
539 indCols_idxStrip = new int[ptRows[dim]];
540 indCols_idxSbdmn = new int[ptRows[dim]];
541
542 for (int n = (_nbLevels - 1); n >=0; n--) {
543 unsigned begDom = (1 << n);
544 unsigned endDom = 2 * begDom; // (1 << (n + 1));
545 unsigned dd;
546 for (unsigned d = begDom; d < endDom; d++) {
547 const unsigned d1 = d - 1; // to access C array
548 for (unsigned i = _ptOnDomains[d1];
549 i < (_ptOnDomains[d1] + _sizeOfDomains[d1]);
550 i++) {
551 for (int m = 0; m <= n; m++) {
552 indCols_bylvl[m].clear();
553 }
554 const int ii = _local2global[i];
555 for (int k = ptRows[ii]; k < ptRows[ii + 1]; k++) {
556 const int j = indCols[k];
557 const int jj = _global2local[j];
558 dd = l2d[jj];
559 if (dd <= d) {
560 unsigned ndl = nodeLayer(dd);
561 indCols_bylvl[ndl].insert(std::map<int,int>::value_type(jj, k));
562 }
563 } // loop : k
564 // m == n : diagonal
565 dd = d;
566 for (std::map<int, int>::iterator it = indCols_bylvl[n].begin();
567 it != indCols_bylvl[n].end();
568 ++it) {
569 indCols_sbdmn[(*it).second] = dd;
570 indCols_idxStrip[(*it).second] = // within one strip
571 indCols_idxSbdmn[(*it).second] =
572 ((*it).first - _ptOnDomains[dd - 1]);
573 }
574 for (int m = (n - 1); m >= 0; m--) {
575 dd /= 2;
576 const unsigned dd1 = dd - 1;
577 SetOfStrips::iterator is = _interco[d1][m].begin();
578 int width_strips = 0;
579 for (std::map<int, int>::iterator it = indCols_bylvl[m].begin();
580 it != indCols_bylvl[m].end();
581 ++it) {
582 int endStrip = ((*is).begin_dst + _ptOnDomains[dd1] +
583 (*is).width);
584 while (endStrip < (*it).first) {
585 width_strips += (*is).width;
586 ++is;
587 if (is == _interco[d1][m].end()) {
588 }
589 else {
590 endStrip = ((*is).begin_dst + _ptOnDomains[dd1] +
591 (*is).width);
592 }
593 }
594 const int begStrip = (*is).begin_dst + _ptOnDomains[dd1];
595 if ((begStrip <= (*it).first) && ((*it).first < endStrip)) {
596 indCols_sbdmn[(*it).second] = dd;
597 indCols_idxStrip[(*it).second] =
598 (((*it).first - begStrip) + width_strips);
599 indCols_idxSbdmn[(*it).second] =
600 ((*it).first - _ptOnDomains[dd1]);
601 }
602 } // loop : it
603 } // loop : m
604 } // loop : i
605 }
606 }
607
608 //
609 // gnereating map from diagonal matrix / offdiagonal strips to matrix value
610 // in original CSR format
611 int itmp = 0;
612 for (int d = 0; d < nbDoms; d++) {
613 if (itmp < _sizeOfDomains[d]) {
614 itmp = _sizeOfDomains[d];
615 }
616 }
617 diss_printf(verbose, fp, "max of size of subdomains = %d\n", itmp);
618 std::map<int, int> *sparse_row_diag = new std::map<int, int>[itmp];
619 std::map<int, int> *sparse_row_offdiag = new std::map<int, int>[itmp];
620
621 _csr_diag = new CSR_indirect[nbDoms];
622 _csr_offdiag = new CSR_indirect[nbDoms];
623 _sizeOfFathersStrips = new int[nbDoms];
624
625 int *width_strips_sbdmn = new int[_nbLevels];
626
627 for (int n = (_nbLevels - 1); n >=0; n--) {
628 unsigned begDom = (1 << n);
629 unsigned endDom = 2 * begDom; // (1 << (n + 1));
630 for (unsigned d = begDom; d < endDom; d++) {
631 const int d1 = d - 1;
632 for (int m = nodeLayer(d) - 1; m >= 0; m--) {
633 width_strips_sbdmn[m] = 0;
634 }
635 for (int m = (nodeLayer(d) - 1); m > 0; m--) {
636 width_strips_sbdmn[m - 1] = width_strips_sbdmn[m];
637 for (SetOfStrips::iterator it = _interco[d1][m].begin();
638 it != _interco[d1][m].end(); ++it) {
639 width_strips_sbdmn[m - 1] += (*it).width;
640 }
641 }
642 for (int i = 0; i < _sizeOfDomains[d1]; i++) {
643 sparse_row_diag[i].clear();
644 sparse_row_offdiag[i].clear();
645 }
646 int ii0, ii;
647 for (ii0 = 0, ii = _ptOnDomains[d1];
648 ii0 < _sizeOfDomains[d1];
649 ii++, ii0++) {
650 const int i = _local2global[ii];
651
652 for (int k = ptRows[i]; k < ptRows[i + 1]; k++) {
653 int jj = _global2local[indCols[k]];
654 unsigned dd = l2d[jj];
655 if (dd == d) {
656 #ifdef DEBUG_MAPPING_CSR
657 sparse_row_diag[ii0].insert(std::map<int, int>::value_type(indCols_idxStrip[k], k));
658 #else
659 sparse_row_diag[ii0].insert(std::map<int, int>::value_type(indCols_idxStrip[k], k)); //(isLower ? toSym[k] : k)));
660 #endif
661 }
662 else {
663 if (dd < d) {
664 #ifdef DEBUG_MAPPING_CSR
665 sparse_row_offdiag[ii0].insert(std::map<int, int>::value_type(indCols_idxStrip[k] + width_strips_sbdmn[nodeLayer(dd)], k));
666 #else
667 sparse_row_offdiag[ii0].insert(std::map<int, int>::value_type(indCols_idxStrip[k] + width_strips_sbdmn[nodeLayer(dd)], k)); //(isLower ? toSym[k] : k)));
668 #endif
669 }
670 }
671 } // loop : k
672 } // loop : ii, ii0
673 _csr_diag[d1].n = _sizeOfDomains[d1];
674 _csr_offdiag[d1].n = _sizeOfDomains[d1];
675 _csr_diag[d1].ptRows = new int [_csr_diag[d1].n + 1];
676 _csr_offdiag[d1].ptRows = new int [_csr_offdiag[d1].n + 1];
677 _csr_diag[d1].ptRows[0] = 0;
678 _csr_offdiag[d1].ptRows[0] = 0;
679 for (int i = 0; i < _csr_diag[d1].n; i++) {
680 _csr_diag[d1].ptRows[i + 1] = (_csr_diag[d1].ptRows[i] +
681 sparse_row_diag[i].size());
682 _csr_offdiag[d1].ptRows[i + 1] = (_csr_offdiag[d1].ptRows[i] +
683 sparse_row_offdiag[i].size());
684 }
685 _csr_diag[d1].nnz = _csr_diag[d1].ptRows[_csr_diag[d1].n];
686 _csr_offdiag[d1].nnz = _csr_offdiag[d1].ptRows[_csr_offdiag[d1].n];
687 _csr_diag[d1].indCols = new int [_csr_diag[d1].nnz];
688 _csr_offdiag[d1].indCols = new int [_csr_offdiag[d1].nnz];
689 _csr_diag[d1].indVals = new int [_csr_diag[d1].nnz];
690 _csr_offdiag[d1].indVals = new int [_csr_offdiag[d1].nnz];
691 _csr_diag[d1].indVals0 = new int [_csr_diag[d1].nnz];
692 _csr_offdiag[d1].indVals0 = new int [_csr_offdiag[d1].nnz];
693 if(!isSym) {
694 _csr_offdiag[d1].indVals_unsym = new int [_csr_offdiag[d1].nnz];
695 }
696 #ifdef DEBUG_MAPPING_CSR
697 _csr_diag[d1].indVals2 = new int [_csr_diag[d1].nnz];
698 _csr_offdiag[d1].indVals2 = new int [_csr_offdiag[d1].nnz];
699 #endif
700 int k0, k1;
701 k0 = 0;
702 k1 = 0;
703
704 for (int i = 0; i < _csr_diag[d1].n; i++){
705 for (std::map<int, int>::iterator it = sparse_row_diag[i].begin();
706 it != sparse_row_diag[i].end(); ++it, k0++) {
707 _csr_diag[d1].indCols[k0] = (*it).first;
708 #ifdef DEBUG_MAPPING_CSR
709 _csr_diag[d1].indVals2[k0] = (*it).second;
710 _csr_diag[d1].indVals[k0] = toSym[(*it).second];
711 #else
712 _csr_diag[d1].indVals0[k0] = (*it).second; //map_indcols[(*it).second];
713 _csr_diag[d1].indVals[k0] = indVals[(*it).second]; //remap_indcols[(*it).second];
714 #endif
715 }
716 for (std::map<int, int>::iterator it = sparse_row_offdiag[i].begin();
717 it != sparse_row_offdiag[i].end(); ++it, k1++) {
718 _csr_offdiag[d1].indCols[k1] = (*it).first;
719 #ifdef DEBUG_MAPPING_CSR
720 _csr_offdiag[d1].indVals2[k1] = (*it).second;
721 _csr_offdiag[d1].indVals[k1] = toSym[(*it).second];
722 #else
723 _csr_offdiag[d1].indVals0[k1] = (*it).second; //remap_indcols[(*it).second];
724 _csr_offdiag[d1].indVals[k1] = indVals[(*it).second]; //remap_indcols[(*it).second];
725 #endif
726 }
727 }
728 if (!isSym) {
729 int k = 0;
730 for (int i = 0; i < _csr_diag[d1].n; i++){
731 for (std::map<int, int>::iterator it = sparse_row_offdiag[i].begin();
732 it != sparse_row_offdiag[i].end(); ++it, k++) {
733 _csr_offdiag[d1].indVals_unsym[k] = unsym_upper2lower[(*it).second];
734 // unsym_upper2lower[(*it).second];
735 }
736 }
737 } // if (!isSym)
738 } // loop : d
739 } // loop : n
740
741
742 delete [] sparse_row_diag;
743 delete [] sparse_row_offdiag;
744 // delete [] l2d;
745 #if 0
746 fich = fopen("sparseMatrix4.dat", "w");
747 fprintf(fich, "dim = %d\n", dim);
748 fprintf(fich, "# of subdomais = %d\n", nbDoms);
749 for (int d = 0; d < nbDoms; d++) {
750 fprintf(fich, "subdomain = %d : %d diagonal n = %d nnz = %d\n",
751 d, _sizeOfDomains[d],
752 _csr_diag[d].n, _csr_diag[d].nnz);
753 for (int i = 0; i < (_csr_diag[d].n + 1); i++) {
754 fprintf(fich, "%d ", _csr_diag[d].ptRows[i]);
755 }
756 fprintf(fich, "\n");
757 for (int i = 0; i < _csr_diag[d].n; i++) {
758 for (int k = _csr_diag[d].ptRows[i];
759 k < _csr_diag[d].ptRows[i + 1];
760 k++) {
761 fprintf(fich, "(%d %d) ",
762 _csr_diag[d].indCols[k], _csr_diag[d].indVals0[k]);
763 }
764 }
765 fprintf(fich, "\n");
766 fprintf(fich, "subdomain = %d : %d offdiagonal n = %d nnz = %d\n",
767 d, _sizeOfDomains[d],
768 _csr_offdiag[d].n, _csr_offdiag[d].nnz);
769 for (int i = 0; i < (_csr_offdiag[d].n + 1); i++) {
770 fprintf(fich, "%d ", _csr_offdiag[d].ptRows[i]);
771 }
772 fprintf(fich, "\n");
773 for (int i = 0; i < _csr_offdiag[d].n; i++) {
774 for (int k = _csr_offdiag[d].ptRows[i];
775 k < _csr_offdiag[d].ptRows[i + 1];
776 k++) {
777 fprintf(fich, "(%d %d) ",
778 _csr_offdiag[d].indCols[k], _csr_offdiag[d].indVals0[k]);
779 }
780 }
781 fprintf(fich, "\n");
782 } // loop : d
783 #endif
784 _nbDoms = nbDoms;
785 for (int d = 0; d < nbDoms; d++) {
786 _sizeOfFathersStrips[d] = 0;
787 int level = nodeLayer(d + 1);
788 for (int m = level - 1; m >= 0; m--) {
789 SetOfStrips &strps = _interco[d][level - 1 - m];
790 _sizeOfFathersStrips[d] += strps.numberOfIndices();
791 }
792 }
793
794 // Create glob 2 dom links :
795 _glob2dom = new int[dim];
796 for (unsigned iDom = 0; iDom < (1<<_nbLevels)-1; iDom++) {
797 for (unsigned iNode = _ptOnDomains[iDom];
798 iNode < _ptOnDomains[iDom+1]; iNode++) {
799 _glob2dom[_local2global[iNode]] = iDom + 1;
800 }
801 }
802
803 _loc2glob_diag = new int*[nbDoms];
804 _loc2glob_offdiag = new int *[nbDoms];
805 for (int d = 0; d < nbDoms; d++) {
806 _loc2glob_diag[d] = new int[_sizeOfDomains[d]];
807 int ii = _ptOnDomains[d];
808 for (int i = 0; i < _sizeOfDomains[d]; i++, ii++) {
809 // _loc2glob_diag[d][i] = _local2global[ii];
810 // 16 Jul.2013 Atsushi getDiagLoc2Glob(nd)[] = loc2glob_diag[nd][]
811 _loc2glob_diag[d][i] = remap_eqn[_local2global[ii]]; // _local2global[ii]; //
812 // 19 Dec.
813 }
814 int itmp = 0;
815 FathersStrips &fstrps = _interco[d];
816 const int layer = nodeLayer(d + 1);
817 for (int m = (layer - 1); m >= 0; m--) {
818 itmp += fstrps[m].numberOfIndices();
819 }
820 _loc2glob_offdiag[d] = new int[_sizeOfFathersStrips[d]];
821 int i0 = 0; // index inside of strips which are stored contiguously
822 for (int m = (layer - 1); m >= 0; m--) {
823 for (SetOfStrips::iterator it = fstrps[m].begin();
824 it != fstrps[m].end(); ++it) {
825 const int n = nthfatherIndex((d + 1), (layer - m));
826 ii = (_ptOnDomains[n - 1] + (*it).begin_dst);
827 for (int j = 0; j < (*it).width; j++, i0++, ii++) {
828 // _loc2glob_offdiag[d][i0] = _local2global[ii];
829 // 16 Jul.2013 Atsushi getOffdiagLoc2Glob(nd)[] = loc2glob_offdiag[nd][]
830 _loc2glob_offdiag[d][i0] = remap_eqn[_local2global[ii]]; // _local2global[ii];
831 // 19 Dec.
832 }
833 }
834 }
835 }
836
837
838 // Destroy temporary data
839 for (int d = 0; d < nbDoms; d++) {
840 delete [] _csr_diag[d].indVals0;
841 delete [] _csr_offdiag[d].indVals0;
842 _csr_diag[d].indVals0 = NULL;
843 _csr_offdiag[d].indVals0 = NULL;
844 }
845 for (unsigned iDom = 2; iDom <= nbDoms; iDom++) {
846 delete [] stripConnections[iDom-1];
847 delete [] connections[iDom-1];
848 }
849 delete [] stripConnections;
850 delete [] connections;
851 delete [] loc2dom;
852 delete [] indCols2;
853 delete [] ptRows2 ;
854 delete [] l2d;
855 // 01 Feb.2013 : Atsushi -- begin
856 delete [] indVals_tmp;
857 delete [] ptRow_diag;
858 delete [] indCols_bylvl;
859 delete [] indCols_sbdmn;
860 delete [] indCols_idxStrip;
861 delete [] indCols_idxSbdmn;
862 delete [] width_strips_sbdmn;
863 // 01 Feb.2013 : Atsushi -- end
864 berr = true;
865 }
866 // --------------------------------------------------------------
867 Tree::~Tree()
868 {
869 delete [] _sizeOfDomains;
870 delete [] _ptOnDomains;
871 delete [] _local2global;
872 delete [] _global2local;
873 if (_interco) delete [] _interco;
874 //unsigned nDoms = (1<<_nbLevels)-1;
875 // 01 Feb.2013 : Atsushi -- begin
876 delete [] _glob2dom;
877 delete [] _sizeOfFathersStrips;
878 for (int i = 0; i < _nbDoms; i++) {
879 delete [] _loc2glob_diag[i];
880 delete [] _loc2glob_offdiag[i];
881 delete [] _csr_diag[i].ptRows;
882 delete [] _csr_diag[i].indCols;
883 delete [] _csr_diag[i].indVals;
884 // delete [] _csr_diag[i].indVals0;
885 delete [] _csr_offdiag[i].ptRows;
886 delete [] _csr_offdiag[i].indCols;
887 delete [] _csr_offdiag[i].indVals;
888 // delete [] _csr_offdiag[i].indVals0;
889 }
890 if (!_isSym) {
891 for (int i = 0; i < _nbDoms; i++) {
892 delete [] _csr_offdiag[i].indVals_unsym;
893 }
894 }
895 delete [] _loc2glob_diag;
896 delete [] _loc2glob_offdiag;
897 delete [] _csr_diag;
898 delete [] _csr_offdiag;
899 // 01 Feb.2013 : Atsushi -- end
900 }
901 // ==============================================================
902 bool
903 Tree::save(FILE* stream) const
904 {
905 // To do
906 return true;
907 }
908 // --------------------------------------------------------------
909 bool
910 Tree::load(FILE* stream)
911 {
912 // To do
913 return true;
914 }
915 // --------------------------------------------------------------
916 void
917 Tree::printInfo(FILE* stream, unsigned verboseLevel) const
918 {
919 unsigned l,n,p;
920 fprintf(stream,"Number of bisection level : %u\n",_nbLevels);
921 for (l=0; l < _nbLevels; l++) {
922 double meanSize = 0., varSize = 0.;
923 for (n = 1<<l; n < 1<<(l+1); n++) {
924 unsigned szDom = sizeOfDomain(n);
925 meanSize += szDom;
926 varSize += szDom*szDom;
927 }
928 meanSize /= (1<<l);
929 varSize = varSize/(1<<l) - meanSize*meanSize;
930 fprintf(stream, "Mean number of nodes at level %u : %lg\n",l,
931 meanSize);
932 fprintf(stream,
933 "Variance for number of nodes at level %u : %lg\n",
934 l, varSize);
935 }
936 if (verboseLevel <= 1) return;
937 for (n=1; n < (1<<_nbLevels); n++) {
938 unsigned idxStart = _ptOnDomains[n-1];
939 unsigned idxEnd = idxStart + sizeOfDomain(n);
940 fprintf(stream,
941 "Global index of %d nodes in subdomain %u :\n",
942 _sizeOfDomains[n-1],n);
943 for (p=idxStart; p < idxEnd; p++) {
944 fprintf(stream,"%d\t",_local2global[p]);
945 }
946 fprintf(stream, "\n");
947 }
948 }
949 // ==============================================================
950 void
951 Tree::removeLoops(int dim,
952 const int* ptRows, const int* indCols,
953 int*& ptRows2, int*& indCols2)
954 {
955 // Optimize with bsearch or equivalent ?
956 int nz = ptRows[dim];
957 ptRows2 = new int[dim+1];
958 indCols2= new int[nz-dim];
959 ptRows2[dim] = nz-dim;
960 for (int iRow = 0; iRow < dim; iRow++) {
961 ptRows2[iRow] = ptRows[iRow]-iRow;
962 int jColInd2 = ptRows2[iRow];
963 for (int jColInd = ptRows[iRow];
964 jColInd < ptRows[iRow+1];
965 jColInd++)
966 {
967 if (indCols[jColInd] != iRow) {
968 indCols2[jColInd2] = indCols[jColInd];
969 jColInd2++;
970 CHECK(jColInd2<=nz-dim,
971 "jColInd2 is greater than number of non zero elements !");
972 }
973 }
974 }
975 }
976 // ==============================================================
977 FathersStrips*
978 Tree::symbolicFactorization(SetOfStrips** connections)
979 {
980 bool verbose = false;
981 unsigned iLevel, iDom, layer, iLayer, jLayer;
982 unsigned nbDoms = (1U<<_nbLevels)-1;
983 diss_printf(verbose, stderr, "nbDoms = %d\n", nbDoms);
984 // Initialize initial filling for each block :
985 FathersStrips* factConnect = new FathersStrips[nbDoms];
986 assert(factConnect != NULL);
987 for (iDom = 2; iDom <= nbDoms; iDom++)
988 {// For iDom==1, nothing to do...
989 layer = nodeLayer(iDom);
990 diss_printf(verbose, stderr, "iDom %d at level %d\n", iDom, layer);
991 factConnect[iDom-1].alloc(layer);
992 for (iLayer = 0; iLayer < layer; iLayer++)
993 {
994 diss_printf(verbose, stderr, "initial connection for %d with layer %d\n",
995 iDom, iLayer);
996 // Initial connection block with his ancestors :
997 factConnect[iDom-1][iLayer] = connections[iDom-1][iLayer];
998 }
999 }
1000 // Start symbolic factorization :
1001 for (iLevel = _nbLevels-1; iLevel > 0; iLevel--)
1002 {
1003 // First domain indice for this level:
1004 unsigned begDom = (1<<iLevel);
1005 // Last domain indice for this level + 1:
1006 unsigned endDom = 2*begDom;
1007 // Gauss symbolic elimination for each domain iDom at level iLevel
1008 for (iDom = begDom; iDom < endDom; iDom++)
1009 {
1010 diss_printf(verbose, stderr, "Eliminating dom %d \n", iDom);
1011 unsigned ancestDom = iDom;
1012 for (iLayer = iLevel-1; iLayer > 0; iLayer--) {
1013 ancestDom = ancestDom/2;// Compute indice (starting to 1)
1014 // of next ancestor :
1015 diss_printf(verbose, stderr,
1016 "ancestDom = %d\niLayer = %d\n", ancestDom, iLayer);
1017 for (jLayer = iLayer; jLayer > 0; jLayer--) {
1018 diss_printf(verbose, stderr, "jLayer = %d\n", (jLayer - 1));
1019 factConnect[ancestDom-1][jLayer-1] +=
1020 factConnect[iDom-1][jLayer-1];
1021 }
1022 }
1023 }
1024 }
1025 // end symbolic factorization
1026 // ............................................................
1027 # if defined(DISSECTION_DEBUG)
1028 // DEBUGGING : Save filling of the matrix
1029 FILE* fich = fopen("filledMatrix.dat", "w");
1030 fprintf(fich,"%d\n",_nbLevels);
1031 for (iDom = 0; iDom < nbDoms; iDom++)
1032 fprintf(fich,"%d %d\n",_ptOnDomains[iDom],
1033 _sizeOfDomains[iDom]);
1034 // ancestors connection :
1035 for (iLevel = 1; iLevel < _nbLevels; iLevel++)
1036 {
1037 // First domain indice for this level:
1038 unsigned begDom = (1<<iLevel);
1039 // Last domain indice for this level + 1:
1040 unsigned endDom = 2*begDom;
1041 for (iDom = begDom; iDom < 2*begDom; iDom++) {
1042 for (iLayer = 0; iLayer < iLevel; iLayer++) {
1043 fprintf(fich,"%d\t",factConnect[iDom-1][iLayer].numberOfStrips());
1044 for (SetOfStrips::iterator itS = factConnect[iDom-1][iLayer].begin();
1045 itS != factConnect[iDom-1][iLayer].end(); itS++) {
1046 fprintf(fich, "%d %d\t",(*itS).begin_dst, (*itS).width);
1047 }
1048 fprintf(fich,"\n");
1049 }// for iLayer
1050 }// for iDom
1051 }// for iLevel
1052 fclose(fich);
1053 # endif
1054 return factConnect;
1055 }
1056
1057 void Tree::draw_csr(char *filename,
1058 int dim,
1059 const int *ptRows,
1060 const int *indCols,
1061 const int *ptRow_diag,
1062 const int *indVals,
1063 const unsigned *l2d)
1064 {
1065 FILE *fp;
1066 char color[256];
1067 double xscale, yscale;
1068 double xpos, ypos;
1069 int *posDom = new int[_nbDoms];
1070 xscale = yscale = 380.0 / (double)(dim + 2);
1071 xpos = 10.0;
1072 ypos = 390.0;
1073 if((fp = fopen(filename, "w")) == NULL) {
1074 exit(-1);
1075 }
1076 fprintf(fp, "%%!PS-Adobe-3.0 EPSF-3.0\n%%%%BoundingBox: 5 5 395 395\n");
1077 fprintf(fp, "/rr { %g } def\n",
1078 0.05 < (xscale * 0.45) ? 0.05 : (xscale *0.45));
1079 // fprintf(fp, "/rrr { %g } def\n", 0.5);
1080 fprintf(fp, "/n { newpath } def\n");
1081 fprintf(fp, "/c { closepath } def\n");
1082 fprintf(fp, "/s { 0.01 setlinewidth stroke } def\n");
1083 fprintf(fp, "/f { fill } def\n");
1084 fprintf(fp, "/sfill { 0.01 setlinewidth fill } def\n");
1085 fprintf(fp, "/gs { gsave } def\n");
1086 fprintf(fp, "/gr { grestore } def\n");
1087 fprintf(fp, "/rl { rlineto } def\n");
1088 fprintf(fp, "/m { moveto } def\n");
1089 fprintf(fp, "/black { 0 0 0 setrgbcolor } def\n");
1090 fprintf(fp, "/red { 1 0 0 setrgbcolor } def\n");
1091 fprintf(fp, "/green { 0 1 0 setrgbcolor } def\n");
1092 fprintf(fp, "/blue { 0 0 1 setrgbcolor } def\n");
1093 fprintf(fp, "/yellow { 1 1 0 setrgbcolor } def\n");
1094 fprintf(fp, "/magenta { 1 0 1 setrgbcolor } def\n");
1095 fprintf(fp, "/cyan { 0 1 1 setrgbcolor } def\n");
1096 fprintf(fp, "/darkgreen { 0 0.5 0 setrgbcolor } def\n");
1097 fprintf(fp, "/gray95 { 0.95 setgray } def\n");
1098 fprintf(fp, "/graycyan { 0.2 0.6 0.6 setrgbcolor } def\n");
1099 fprintf(fp, "n 10 10 m 380 0 rl 0 380 rl -380 0 rl 0 -380 rl c gray95 fill\n");
1100 int pos = 0;
1101 int dense = 0;
1102 posDom[0] = 0;
1103 for (int n = (_nbLevels - 1); n >=0; n--) {
1104 unsigned begDom = (1 << n);
1105 unsigned endDom = 2 * begDom; // (1 << (n + 1));
1106 for (unsigned d = begDom; d < endDom; d++) {
1107 const int d1 = d - 1;
1108 posDom[d1] = pos;
1109 pos += _sizeOfDomains[d1];
1110 }
1111 }
1112 // drawing position of non-zero elemnet laying over domain decompositions
1113 //strcpy(color, "yellow");
1114 for (int n = (_nbLevels - 1); n >=0; n--) {
1115 unsigned begDom = (1 << n);
1116 unsigned endDom = 2 * begDom; // (1 << (n + 1));
1117 for (unsigned d = begDom; d < endDom; d++) {
1118 const int d1 = d - 1;
1119 int dd = d;
1120 if (n == (_nbLevels - 1)) {
1121 strcpy(color, "blue");
1122 }
1123 else {
1124 strcpy(color, "red");
1125 dense += _sizeOfDomains[d1] * _sizeOfDomains[d1];
1126 }
1127 fprintf(fp, "n %g %g m %g 0 rl 0 %g rl %g 0 rl c gs %s f gr %s s\n",
1128 xpos + (double)posDom[d1] * xscale,
1129 ypos - (double)(posDom[d1] + _sizeOfDomains[d1]) * yscale,
1130 _sizeOfDomains[d1] * xscale,
1131 (double)_sizeOfDomains[d1] * yscale,
1132 (-1.0) * (double)_sizeOfDomains[d1] * xscale,
1133 color, color);
1134
1135 dd = d;
1136 if (n == (_nbLevels - 1)) {
1137 strcpy(color, "darkgreen");
1138 }
1139 else {
1140 strcpy(color, "graycyan");
1141 }
1142 for (int m = (n - 1); m >= 0; m--) {
1143 dd /= 2;
1144 const unsigned dd1 = dd - 1;
1145 for (SetOfStrips::iterator it = _interco[d1][m].begin();
1146 it != _interco[d1][m].end(); ++it) {
1147 fprintf(fp, "n %g %g m %g 0 rl 0 %g rl %g 0 rl c gs %s f gr %s s\n",
1148 xpos + (double)(posDom[dd1] + (*it).begin_dst) * xscale,
1149 ypos - (double)(posDom[d1] + _sizeOfDomains[d1]) * yscale,
1150 (double)(*it).width * xscale,
1151 (double)_sizeOfDomains[d1] * yscale,
1152 (-1.0) * (double)(*it).width * xscale,
1153 color, color);
1154 if (n < (_nbLevels - 1)) {
1155 dense += _sizeOfDomains[d1] * (*it).width;
1156 }
1157 }
1158 }
1159 }
1160 } // loop : n
1161 #if 1
1162 int k = 0;
1163 for (int i = 0; i < dim; i++) {
1164 for (int kk = ptRow_diag[i]; kk < ptRows[i + 1]; kk++, k++) {
1165 switch (indVals[k]) {
1166 case 0 :
1167 strcpy(color, "red");
1168 break;
1169 case 1:
1170 strcpy(color, "black");
1171 break;
1172 case 2:
1173 strcpy(color, "cyan");
1174 break;
1175 default:
1176 strcpy(color, "green");
1177 break;
1178 }
1179 int j = indCols[kk];
1180 #if 1
1181 int ii = _global2local[i];
1182 int jj = _global2local[j];
1183 int di = l2d[ii];
1184 int dj = l2d[jj];
1185 #else
1186 unsigned ii, jj, di, dj;
1187 getGlob2Loc_dom(i, ii, di);
1188 getGlob2Loc_dom(j, jj, dj);
1189 #endif
1190 if (dj > di) {
1191 int itmp;
1192 itmp = ii;
1193 ii = jj;
1194 jj = itmp;
1195 itmp = di;
1196 di = dj;
1197 dj = itmp;
1198 if (indVals[k] == 0) {
1199 strcpy(color, "magenta");
1200 }
1201 }
1202
1203 fprintf(fp,"n %g %g rr 0 360 arc %s sfill\n",
1204 xpos +
1205 ((double)(jj - _ptOnDomains[dj - 1] + posDom[dj - 1]) + 0.5) * xscale,
1206 ypos - ((double)(ii - _ptOnDomains[di - 1] + posDom[di - 1]) + 0.5) * yscale,
1207 color);
1208 if (dj == di) {
1209 strcpy(color, "graycyan");
1210 fprintf(fp,"n %g %g rr 0 360 arc %s sfill\n",
1211 xpos + ((double)(ii - _ptOnDomains[di - 1] + posDom[di - 1]) + 0.5) * xscale,
1212 ypos - ((double)(jj - _ptOnDomains[di - 1] + posDom[di - 1]) + 0.5) * yscale,
1213 color);
1214 }
1215 }
1216 }
1217 #endif
1218 fprintf(fp, "%%dense=%d\n", dense);
1219 fprintf(fp, "showpage\n");
1220 fclose(fp);
1221 }