1 #include <petsc-private/dmpleximpl.h> /*I "petscdmplex.h" I*/ 2 #include <petscsf.h> 3 4 #undef __FUNCT__ 5 #define __FUNCT__ "DMPlexReverseCell" 6 /*@ 7 DMPlexReverseCell - Give a mesh cell the opposite orientation 8 9 Input Parameters: 10 + dm - The DM 11 - cell - The cell number 12 13 Note: The modification of the DM is done in-place. 14 15 Level: advanced 16 17 .seealso: DMPlexOrient(), DMCreate(), DMPLEX 18 @*/ 19 PetscErrorCode DMPlexReverseCell(DM dm, PetscInt cell) 20 { 21 /* Note that the reverse orientation ro of a face with orientation o is: 22 23 ro = o >= 0 ? -(faceSize - o) : faceSize + o 24 25 where faceSize is the size of the cone for the face. 26 */ 27 const PetscInt *cone, *coneO, *support; 28 PetscInt *revcone, *revconeO; 29 PetscInt maxConeSize, coneSize, supportSize, faceSize, cp, sp; 30 PetscErrorCode ierr; 31 32 PetscFunctionBegin; 33 ierr = DMPlexGetMaxSizes(dm, &maxConeSize, NULL);CHKERRQ(ierr); 34 ierr = DMGetWorkArray(dm, maxConeSize, PETSC_INT, &revcone);CHKERRQ(ierr); 35 ierr = DMGetWorkArray(dm, maxConeSize, PETSC_INT, &revconeO);CHKERRQ(ierr); 36 /* Reverse cone, and reverse orientations of faces */ 37 ierr = DMPlexGetConeSize(dm, cell, &coneSize);CHKERRQ(ierr); 38 ierr = DMPlexGetCone(dm, cell, &cone);CHKERRQ(ierr); 39 ierr = DMPlexGetConeOrientation(dm, cell, &coneO);CHKERRQ(ierr); 40 for (cp = 0; cp < coneSize; ++cp) { 41 const PetscInt rcp = coneSize-cp-1; 42 43 ierr = DMPlexGetConeSize(dm, cone[rcp], &faceSize);CHKERRQ(ierr); 44 revcone[cp] = cone[rcp]; 45 revconeO[cp] = coneO[rcp] >= 0 ? -(faceSize-coneO[rcp]) : faceSize+coneO[rcp]; 46 } 47 ierr = DMPlexSetCone(dm, cell, revcone);CHKERRQ(ierr); 48 ierr = DMPlexSetConeOrientation(dm, cell, revconeO);CHKERRQ(ierr); 49 /* Reverse orientation of this cell in the support hypercells */ 50 faceSize = coneSize; 51 ierr = DMPlexGetSupportSize(dm, cell, &supportSize);CHKERRQ(ierr); 52 ierr = DMPlexGetSupport(dm, cell, &support);CHKERRQ(ierr); 53 for (sp = 0; sp < supportSize; ++sp) { 54 ierr = DMPlexGetConeSize(dm, support[sp], &coneSize);CHKERRQ(ierr); 55 ierr = DMPlexGetCone(dm, support[sp], &cone);CHKERRQ(ierr); 56 ierr = DMPlexGetConeOrientation(dm, support[sp], &coneO);CHKERRQ(ierr); 57 for (cp = 0; cp < coneSize; ++cp) { 58 if (cone[cp] != cell) continue; 59 ierr = DMPlexInsertConeOrientation(dm, support[sp], cp, coneO[cp] >= 0 ? -(faceSize-coneO[cp]) : faceSize+coneO[cp]);CHKERRQ(ierr); 60 } 61 } 62 ierr = DMRestoreWorkArray(dm, maxConeSize, PETSC_INT, &revcone);CHKERRQ(ierr); 63 ierr = DMRestoreWorkArray(dm, maxConeSize, PETSC_INT, &revconeO);CHKERRQ(ierr); 64 PetscFunctionReturn(0); 65 } 66 67 #undef __FUNCT__ 68 #define __FUNCT__ "DMPlexOrient" 69 /*@ 70 DMPlexOrient - Give a consistent orientation to the input mesh 71 72 Input Parameters: 73 . dm - The DM 74 75 Note: The orientation data for the DM are change in-place. 76 $ This routine will fail for non-orientable surfaces, such as the Moebius strip. 77 78 Level: advanced 79 80 .seealso: DMCreate(), DMPLEX 81 @*/ 82 PetscErrorCode DMPlexOrient(DM dm) 83 { 84 MPI_Comm comm; 85 PetscBT seenCells, flippedCells, seenFaces; 86 PetscInt *faceFIFO, fTop, fBottom; 87 PetscInt dim, h, cStart, cEnd, c, fStart, fEnd, face; 88 PetscBool flg; 89 PetscErrorCode ierr; 90 91 PetscFunctionBegin; 92 ierr = PetscObjectGetComm((PetscObject) dm, &comm);CHKERRQ(ierr); 93 ierr = PetscOptionsHasName(((PetscObject) dm)->prefix, "-orientation_view", &flg);CHKERRQ(ierr); 94 /* Truth Table 95 mismatch flips do action mismatch flipA ^ flipB action 96 F 0 flips no F F F 97 F 1 flip yes F T T 98 F 2 flips no T F T 99 T 0 flips yes T T F 100 T 1 flip no 101 T 2 flips yes 102 */ 103 ierr = DMGetDimension(dm, &dim);CHKERRQ(ierr); 104 ierr = DMPlexGetVTKCellHeight(dm, &h);CHKERRQ(ierr); 105 ierr = DMPlexGetHeightStratum(dm, h, &cStart, &cEnd);CHKERRQ(ierr); 106 ierr = DMPlexGetHeightStratum(dm, h+1, &fStart, &fEnd);CHKERRQ(ierr); 107 ierr = PetscBTCreate(cEnd - cStart, &seenCells);CHKERRQ(ierr); 108 ierr = PetscBTMemzero(cEnd - cStart, seenCells);CHKERRQ(ierr); 109 ierr = PetscBTCreate(cEnd - cStart, &flippedCells);CHKERRQ(ierr); 110 ierr = PetscBTMemzero(cEnd - cStart, flippedCells);CHKERRQ(ierr); 111 ierr = PetscBTCreate(fEnd - fStart, &seenFaces);CHKERRQ(ierr); 112 ierr = PetscBTMemzero(fEnd - fStart, seenFaces);CHKERRQ(ierr); 113 ierr = PetscMalloc1((fEnd - fStart), &faceFIFO);CHKERRQ(ierr); 114 fTop = fBottom = 0; 115 /* Initialize FIFO with first cell */ 116 if (cEnd > cStart) { 117 const PetscInt *cone; 118 PetscInt coneSize; 119 120 ierr = DMPlexGetConeSize(dm, cStart, &coneSize);CHKERRQ(ierr); 121 ierr = DMPlexGetCone(dm, cStart, &cone);CHKERRQ(ierr); 122 for (c = 0; c < coneSize; ++c) { 123 faceFIFO[fBottom++] = cone[c]; 124 ierr = PetscBTSet(seenFaces, cone[c]-fStart);CHKERRQ(ierr); 125 } 126 } 127 /* Consider each face in FIFO */ 128 while (fTop < fBottom) { 129 const PetscInt *support, *coneA, *coneB, *coneOA, *coneOB; 130 PetscInt supportSize, coneSizeA, coneSizeB, posA = -1, posB = -1; 131 PetscInt seenA, flippedA, seenB, flippedB, mismatch; 132 133 face = faceFIFO[fTop++]; 134 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr); 135 ierr = DMPlexGetSupport(dm, face, &support);CHKERRQ(ierr); 136 if (supportSize < 2) continue; 137 if (supportSize != 2) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Faces should separate only two cells, not %d", supportSize); 138 seenA = PetscBTLookup(seenCells, support[0]-cStart); 139 flippedA = PetscBTLookup(flippedCells, support[0]-cStart) ? 1 : 0; 140 seenB = PetscBTLookup(seenCells, support[1]-cStart); 141 flippedB = PetscBTLookup(flippedCells, support[1]-cStart) ? 1 : 0; 142 143 ierr = DMPlexGetConeSize(dm, support[0], &coneSizeA);CHKERRQ(ierr); 144 ierr = DMPlexGetConeSize(dm, support[1], &coneSizeB);CHKERRQ(ierr); 145 ierr = DMPlexGetCone(dm, support[0], &coneA);CHKERRQ(ierr); 146 ierr = DMPlexGetCone(dm, support[1], &coneB);CHKERRQ(ierr); 147 ierr = DMPlexGetConeOrientation(dm, support[0], &coneOA);CHKERRQ(ierr); 148 ierr = DMPlexGetConeOrientation(dm, support[1], &coneOB);CHKERRQ(ierr); 149 for (c = 0; c < coneSizeA; ++c) { 150 if (!PetscBTLookup(seenFaces, coneA[c]-fStart)) { 151 faceFIFO[fBottom++] = coneA[c]; 152 ierr = PetscBTSet(seenFaces, coneA[c]-fStart);CHKERRQ(ierr); 153 } 154 if (coneA[c] == face) posA = c; 155 if (fBottom > fEnd-fStart) SETERRQ3(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %d was pushed exceeding capacity %d > %d", coneA[c], fBottom, fEnd-fStart); 156 } 157 if (posA < 0) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %d could not be located in cell %d", face, support[0]); 158 for (c = 0; c < coneSizeB; ++c) { 159 if (!PetscBTLookup(seenFaces, coneB[c]-fStart)) { 160 faceFIFO[fBottom++] = coneB[c]; 161 ierr = PetscBTSet(seenFaces, coneB[c]-fStart);CHKERRQ(ierr); 162 } 163 if (coneB[c] == face) posB = c; 164 if (fBottom > fEnd-fStart) SETERRQ3(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %d was pushed exceeding capacity %d > %d", coneA[c], fBottom, fEnd-fStart); 165 } 166 if (posB < 0) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %d could not be located in cell %d", face, support[1]); 167 168 if (dim == 1) { 169 mismatch = posA == posB; 170 } else { 171 mismatch = coneOA[posA] == coneOB[posB]; 172 } 173 174 if (mismatch ^ (flippedA ^ flippedB)) { 175 if (seenA && seenB) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen cells %d and %d do not match: Fault mesh is non-orientable", support[0], support[1]); 176 if (!seenA && !flippedA) { 177 ierr = PetscBTSet(flippedCells, support[0]-cStart);CHKERRQ(ierr); 178 } else if (!seenB && !flippedB) { 179 ierr = PetscBTSet(flippedCells, support[1]-cStart);CHKERRQ(ierr); 180 } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable"); 181 } else if (mismatch && flippedA && flippedB) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable"); 182 ierr = PetscBTSet(seenCells, support[0]-cStart);CHKERRQ(ierr); 183 ierr = PetscBTSet(seenCells, support[1]-cStart);CHKERRQ(ierr); 184 } 185 if (flg) { 186 PetscViewer v; 187 PetscMPIInt rank; 188 189 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr); 190 ierr = PetscViewerASCIIGetStdout(PETSC_COMM_SELF, &v);CHKERRQ(ierr); 191 ierr = PetscViewerASCIISynchronizedAllow(v, PETSC_TRUE);CHKERRQ(ierr); 192 ierr = PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for serial flipped cells:\n", rank);CHKERRQ(ierr); 193 ierr = PetscBTView(cEnd-cStart, flippedCells, v);CHKERRQ(ierr); 194 } 195 /* Now all subdomains are oriented, but we need a consistent parallel orientation */ 196 { 197 /* Find a representative face (edge) separating pairs of procs */ 198 PetscSF sf; 199 const PetscInt *lpoints; 200 const PetscSFNode *rpoints; 201 PetscInt *neighbors, *nranks; 202 PetscInt numLeaves, numRoots, numNeighbors = 0, l, n; 203 204 ierr = DMGetPointSF(dm, &sf);CHKERRQ(ierr); 205 ierr = PetscSFGetGraph(sf, &numRoots, &numLeaves, &lpoints, &rpoints);CHKERRQ(ierr); 206 if (numLeaves >= 0) { 207 const PetscInt *cone, *ornt, *support; 208 PetscInt coneSize, supportSize; 209 int *rornt, *lornt; /* PetscSF cannot handle smaller than int */ 210 PetscBool *match, flipped = PETSC_FALSE; 211 212 ierr = PetscMalloc1(numLeaves,&neighbors);CHKERRQ(ierr); 213 /* I know this is p^2 time in general, but for bounded degree its alright */ 214 for (l = 0; l < numLeaves; ++l) { 215 const PetscInt face = lpoints[l]; 216 if ((face >= fStart) && (face < fEnd)) { 217 const PetscInt rank = rpoints[l].rank; 218 for (n = 0; n < numNeighbors; ++n) if (rank == rpoints[neighbors[n]].rank) break; 219 if (n >= numNeighbors) { 220 PetscInt supportSize; 221 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr); 222 if (supportSize != 1) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Boundary faces should see one cell, not %d", supportSize); 223 neighbors[numNeighbors++] = l; 224 } 225 } 226 } 227 ierr = PetscCalloc4(numNeighbors,&match,numNeighbors,&nranks,numRoots,&rornt,numRoots,&lornt);CHKERRQ(ierr); 228 for (face = fStart; face < fEnd; ++face) { 229 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr); 230 if (supportSize != 1) continue; 231 ierr = DMPlexGetSupport(dm, face, &support);CHKERRQ(ierr); 232 233 ierr = DMPlexGetCone(dm, support[0], &cone);CHKERRQ(ierr); 234 ierr = DMPlexGetConeSize(dm, support[0], &coneSize);CHKERRQ(ierr); 235 ierr = DMPlexGetConeOrientation(dm, support[0], &ornt);CHKERRQ(ierr); 236 for (c = 0; c < coneSize; ++c) if (cone[c] == face) break; 237 if (dim == 1) { 238 /* Use cone position instead, shifted to -1 or 1 */ 239 rornt[face] = c*2-1; 240 } else { 241 if (PetscBTLookup(flippedCells, support[0]-cStart)) rornt[face] = ornt[c] < 0 ? -1 : 1; 242 else rornt[face] = ornt[c] < 0 ? 1 : -1; 243 } 244 } 245 /* Mark each edge with match or nomatch */ 246 ierr = PetscSFBcastBegin(sf, MPI_INT, rornt, lornt);CHKERRQ(ierr); 247 ierr = PetscSFBcastEnd(sf, MPI_INT, rornt, lornt);CHKERRQ(ierr); 248 for (n = 0; n < numNeighbors; ++n) { 249 const PetscInt face = lpoints[neighbors[n]]; 250 251 if (rornt[face]*lornt[face] < 0) match[n] = PETSC_TRUE; 252 else match[n] = PETSC_FALSE; 253 nranks[n] = rpoints[neighbors[n]].rank; 254 } 255 /* Collect the graph on 0 */ 256 { 257 Mat G; 258 PetscBT seenProcs, flippedProcs; 259 PetscInt *procFIFO, pTop, pBottom; 260 PetscInt *adj = NULL; 261 PetscBool *val = NULL; 262 PetscMPIInt *recvcounts = NULL, *displs = NULL, p; 263 PetscMPIInt N = numNeighbors, numProcs = 0, rank; 264 PetscInt debug = 0; 265 266 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr); 267 if (!rank) {ierr = MPI_Comm_size(comm, &numProcs);CHKERRQ(ierr);} 268 ierr = PetscCalloc2(numProcs,&recvcounts,numProcs+1,&displs);CHKERRQ(ierr); 269 ierr = MPI_Gather(&N, 1, MPI_INT, recvcounts, 1, MPI_INT, 0, comm);CHKERRQ(ierr); 270 for (p = 0; p < numProcs; ++p) { 271 displs[p+1] = displs[p] + recvcounts[p]; 272 } 273 if (!rank) {ierr = PetscMalloc2(displs[numProcs],&adj,displs[numProcs],&val);CHKERRQ(ierr);} 274 ierr = MPI_Gatherv(nranks, numNeighbors, MPIU_INT, adj, recvcounts, displs, MPIU_INT, 0, comm);CHKERRQ(ierr); 275 ierr = MPI_Gatherv(match, numNeighbors, MPIU_BOOL, val, recvcounts, displs, MPIU_BOOL, 0, comm);CHKERRQ(ierr); 276 if (debug) { 277 for (p = 0; p < numProcs; ++p) { 278 ierr = PetscPrintf(comm, "Proc %d:\n", p); 279 for (n = 0; n < recvcounts[p]; ++n) { 280 ierr = PetscPrintf(comm, " edge %d (%d):\n", adj[displs[p]+n], val[displs[p]+n]); 281 } 282 } 283 } 284 /* Symmetrize the graph */ 285 ierr = MatCreate(PETSC_COMM_SELF, &G);CHKERRQ(ierr); 286 ierr = MatSetSizes(G, numProcs, numProcs, numProcs, numProcs);CHKERRQ(ierr); 287 ierr = MatSetUp(G);CHKERRQ(ierr); 288 for (p = 0; p < numProcs; ++p) { 289 for (n = 0; n < recvcounts[p]; ++n) { 290 const PetscInt r = p; 291 const PetscInt q = adj[displs[p]+n]; 292 const PetscScalar o = val[displs[p]+n] ? 1.0 : 0.0; 293 294 ierr = MatSetValues(G, 1, &r, 1, &q, &o, INSERT_VALUES);CHKERRQ(ierr); 295 ierr = MatSetValues(G, 1, &q, 1, &r, &o, INSERT_VALUES);CHKERRQ(ierr); 296 } 297 } 298 ierr = MatAssemblyBegin(G, MAT_FINAL_ASSEMBLY);CHKERRQ(ierr); 299 ierr = MatAssemblyEnd(G, MAT_FINAL_ASSEMBLY);CHKERRQ(ierr); 300 301 ierr = PetscBTCreate(numProcs, &seenProcs);CHKERRQ(ierr); 302 ierr = PetscBTMemzero(numProcs, seenProcs);CHKERRQ(ierr); 303 ierr = PetscBTCreate(numProcs, &flippedProcs);CHKERRQ(ierr); 304 ierr = PetscBTMemzero(numProcs, flippedProcs);CHKERRQ(ierr); 305 ierr = PetscMalloc1(numProcs,&procFIFO);CHKERRQ(ierr); 306 pTop = pBottom = 0; 307 for (p = 0; p < numProcs; ++p) { 308 if (PetscBTLookup(seenProcs, p)) continue; 309 /* Initialize FIFO with next proc */ 310 procFIFO[pBottom++] = p; 311 ierr = PetscBTSet(seenProcs, p);CHKERRQ(ierr); 312 /* Consider each proc in FIFO */ 313 while (pTop < pBottom) { 314 const PetscScalar *ornt; 315 const PetscInt *neighbors; 316 PetscInt proc, nproc, seen, flippedA, flippedB, mismatch, numNeighbors; 317 318 proc = procFIFO[pTop++]; 319 flippedA = PetscBTLookup(flippedProcs, proc) ? 1 : 0; 320 ierr = MatGetRow(G, proc, &numNeighbors, &neighbors, &ornt);CHKERRQ(ierr); 321 /* Loop over neighboring procs */ 322 for (n = 0; n < numNeighbors; ++n) { 323 nproc = neighbors[n]; 324 mismatch = PetscRealPart(ornt[n]) > 0.5 ? 0 : 1; 325 seen = PetscBTLookup(seenProcs, nproc); 326 flippedB = PetscBTLookup(flippedProcs, nproc) ? 1 : 0; 327 328 if (mismatch ^ (flippedA ^ flippedB)) { 329 if (seen) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Previously seen procs %d and %d do not match: Fault mesh is non-orientable", proc, nproc); 330 if (!flippedB) { 331 ierr = PetscBTSet(flippedProcs, nproc);CHKERRQ(ierr); 332 } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable"); 333 } else if (mismatch && flippedA && flippedB) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable"); 334 if (!seen) { 335 procFIFO[pBottom++] = nproc; 336 ierr = PetscBTSet(seenProcs, nproc);CHKERRQ(ierr); 337 } 338 } 339 } 340 } 341 ierr = PetscFree(procFIFO);CHKERRQ(ierr); 342 ierr = MatDestroy(&G);CHKERRQ(ierr); 343 344 ierr = PetscFree2(recvcounts,displs);CHKERRQ(ierr); 345 ierr = PetscFree2(adj,val);CHKERRQ(ierr); 346 { 347 PetscBool *flips; 348 349 ierr = PetscMalloc1(numProcs,&flips);CHKERRQ(ierr); 350 for (p = 0; p < numProcs; ++p) { 351 flips[p] = PetscBTLookup(flippedProcs, p) ? PETSC_TRUE : PETSC_FALSE; 352 if (debug && flips[p]) {ierr = PetscPrintf(comm, "Flipping Proc %d:\n", p);} 353 } 354 ierr = MPI_Scatter(flips, 1, MPIU_BOOL, &flipped, 1, MPIU_BOOL, 0, comm);CHKERRQ(ierr); 355 ierr = PetscFree(flips);CHKERRQ(ierr); 356 } 357 ierr = PetscBTDestroy(&seenProcs);CHKERRQ(ierr); 358 ierr = PetscBTDestroy(&flippedProcs);CHKERRQ(ierr); 359 } 360 ierr = PetscFree4(match,nranks,rornt,lornt);CHKERRQ(ierr); 361 ierr = PetscFree(neighbors);CHKERRQ(ierr); 362 if (flipped) {for (c = cStart; c < cEnd; ++c) {ierr = PetscBTNegate(flippedCells, c-cStart);CHKERRQ(ierr);}} 363 } 364 } 365 if (flg) { 366 PetscViewer v; 367 PetscMPIInt rank; 368 369 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr); 370 ierr = PetscViewerASCIIGetStdout(PETSC_COMM_SELF, &v);CHKERRQ(ierr); 371 ierr = PetscViewerASCIISynchronizedAllow(v, PETSC_TRUE);CHKERRQ(ierr); 372 ierr = PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for parallel flipped cells:\n", rank);CHKERRQ(ierr); 373 ierr = PetscBTView(cEnd-cStart, flippedCells, v);CHKERRQ(ierr); 374 } 375 /* Reverse flipped cells in the mesh */ 376 for (c = cStart; c < cEnd; ++c) { 377 if (PetscBTLookup(flippedCells, c-cStart)) {ierr = DMPlexReverseCell(dm, c);CHKERRQ(ierr);} 378 } 379 ierr = PetscBTDestroy(&seenCells);CHKERRQ(ierr); 380 ierr = PetscBTDestroy(&flippedCells);CHKERRQ(ierr); 381 ierr = PetscBTDestroy(&seenFaces);CHKERRQ(ierr); 382 ierr = PetscFree(faceFIFO);CHKERRQ(ierr); 383 PetscFunctionReturn(0); 384 } 385