| 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 |
} |