1 #include <petsc/private/dmpleximpl.h> /*I "petscdmplex.h" I*/
2 #include <petscsf.h>
3
4 /*@
5 DMPlexCompareOrientations - Compare the cone of the given DAG point (cell) with the given reference cone (with the same cone points modulo order), and return relative orientation.
6
7 Not Collective
8
9 Input Parameters:
10 + dm - The DM (DMPLEX)
11 . p - The DAG point whose cone is compared
12 . masterConeSize - Number of the reference cone points passed (at least 2 and at most size of the cone of p)
13 - masterCone - The reference cone points
14
15 Output Parameters:
16 + start - The new starting point within the cone of p to make it conforming with the reference cone
17 - reverse - The flag whether the order of the cone points should be reversed
18
19 Level: advanced
20
21 .seealso: DMPlexOrient(), DMPlexOrientCell()
22 @*/
DMPlexCompareOrientations(DM dm,PetscInt p,PetscInt masterConeSize,const PetscInt masterCone[],PetscInt * start,PetscBool * reverse)23 PetscErrorCode DMPlexCompareOrientations(DM dm, PetscInt p, PetscInt masterConeSize, const PetscInt masterCone[], PetscInt *start, PetscBool *reverse)
24 {
25 PetscInt coneSize;
26 const PetscInt *cone;
27 PetscInt i, start_;
28 PetscBool reverse_;
29 PetscErrorCode ierr;
30
31 PetscFunctionBegin;
32 PetscValidHeaderSpecific(dm, DM_CLASSID, 1);
33 ierr = DMPlexGetConeSize(dm, p, &coneSize);CHKERRQ(ierr);
34 if (coneSize < 2) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Point %D has no cone", p);
35 ierr = DMPlexGetCone(dm, p, &cone);CHKERRQ(ierr);
36 if (masterConeSize < 2) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Point %D: masterConeSize must be at least 2", p);
37 if (masterConeSize > coneSize) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Point %D: masterConeSize must be at most coneSize", p);
38 start_ = 0;
39 for (i=0; i<coneSize; i++) {
40 if (cone[i] == masterCone[0]) {
41 start_ = i;
42 break;
43 }
44 }
45 if (PetscUnlikely(i==coneSize)) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "Point %D: starting point of reference cone not found in slave cone", p);
46 reverse_ = PETSC_FALSE;
47 for (i=0; i<masterConeSize; i++) {if (cone[(start_+i)%coneSize] != masterCone[i]) break;}
48 if (i != masterConeSize) {
49 reverse_ = PETSC_TRUE;
50 for (i=0; i<masterConeSize; i++) {if (cone[(coneSize+start_-i)%coneSize] != masterCone[i]) break;}
51 if (i < masterConeSize) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "Point %D: cone has non-conforming order of points with respect to reference cone", p);
52 }
53 if (start) *start = start_;
54 if (reverse) *reverse = reverse_;
55 if (PetscUnlikely(cone[start_] != masterCone[0])) SETERRQ4(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Point %D: cone[%d] = %d != %d = masterCone[0]", p, start_, cone[start_], masterCone[0]);
56 PetscFunctionReturn(0);
57 }
58
59 /*@
60 DMPlexOrientCell - Set the desired order of cone points of this DAG point, and fix orientations accordingly.
61
62 Not Collective
63
64 Input Parameters:
65 + dm - The DM
66 . p - The DAG point (from interval given by DMPlexGetChart())
67 . masterConeSize - Number of specified cone points (at least 2)
68 - masterCone - Specified cone points, i.e. ordered subset of current cone in DAG numbering (not cone-local numbering)
69
70 Level: intermediate
71
72 .seealso: DMPlexOrient(), DMPlexGetCone(), DMPlexGetConeOrientation(), DMPlexInterpolate(), DMPlexGetChart()
73 @*/
DMPlexOrientCell(DM dm,PetscInt p,PetscInt masterConeSize,const PetscInt masterCone[])74 PetscErrorCode DMPlexOrientCell(DM dm, PetscInt p, PetscInt masterConeSize, const PetscInt masterCone[])
75 {
76 PetscInt coneSize;
77 PetscInt start1=0;
78 PetscBool reverse1=PETSC_FALSE;
79 PetscErrorCode ierr;
80
81 PetscFunctionBegin;
82 PetscValidHeaderSpecific(dm, DM_CLASSID, 1);
83 if (masterConeSize) PetscValidIntPointer(masterCone,4);
84 if (masterConeSize == 1) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "masterConeSize cannot be 1");
85 ierr = DMPlexGetConeSize(dm, p, &coneSize);CHKERRQ(ierr);
86 if (!coneSize) PetscFunctionReturn(0); /* do nothing for points with no cone */
87 ierr = DMPlexCompareOrientations(dm, p, masterConeSize, masterCone, &start1, &reverse1);CHKERRQ(ierr);
88 ierr = DMPlexOrientCell_Internal(dm, p, start1, reverse1);CHKERRQ(ierr);
89 if (PetscDefined(USE_DEBUG)) {
90 PetscInt c;
91 const PetscInt *cone;
92 ierr = DMPlexGetCone(dm, p, &cone);CHKERRQ(ierr);
93 for (c = 0; c < masterConeSize; c++) {
94 if (PetscUnlikely(cone[c] != masterCone[c])) SETERRQ4(PETSC_COMM_SELF, PETSC_ERR_PLIB, "The algorithm above is wrong as cone[%d] = %d != %d = masterCone[%d]", c, cone[c], masterCone[c], c);
95 }
96 }
97 PetscFunctionReturn(0);
98 }
99
DMPlexOrientCell_Internal(DM dm,PetscInt p,PetscInt start1,PetscBool reverse1)100 PetscErrorCode DMPlexOrientCell_Internal(DM dm, PetscInt p, PetscInt start1, PetscBool reverse1)
101 {
102 PetscInt i, j, k, maxConeSize, coneSize, coneConeSize, supportSize, supportConeSize;
103 PetscInt start0, start;
104 PetscBool reverse0, reverse;
105 PetscInt newornt;
106 const PetscInt *cone=NULL, *support=NULL, *supportCone=NULL, *ornts=NULL;
107 PetscInt *newcone=NULL, *newornts=NULL;
108 PetscErrorCode ierr;
109
110 PetscFunctionBegin;
111 if (!start1 && !reverse1) PetscFunctionReturn(0);
112 ierr = DMPlexGetConeSize(dm, p, &coneSize);CHKERRQ(ierr);
113 if (!coneSize) PetscFunctionReturn(0); /* do nothing for points with no cone */
114 ierr = DMPlexGetCone(dm, p, &cone);CHKERRQ(ierr);
115 ierr = DMPlexGetMaxSizes(dm, &maxConeSize, NULL);CHKERRQ(ierr);
116 /* permute p's cone and orientations */
117 ierr = DMPlexGetConeOrientation(dm, p, &ornts);CHKERRQ(ierr);
118 ierr = DMGetWorkArray(dm, maxConeSize, MPIU_INT, &newcone);CHKERRQ(ierr);
119 ierr = DMGetWorkArray(dm, maxConeSize, MPIU_INT, &newornts);CHKERRQ(ierr);
120 ierr = DMPlexFixFaceOrientations_Permute_Private(coneSize, cone, start1, reverse1, newcone);CHKERRQ(ierr);
121 ierr = DMPlexFixFaceOrientations_Permute_Private(coneSize, ornts, start1, reverse1, newornts);CHKERRQ(ierr);
122 /* if direction of p (face) is flipped, flip also p's cone points (edges) */
123 if (reverse1) {
124 for (i=0; i<coneSize; i++) {
125 ierr = DMPlexGetConeSize(dm, cone[i], &coneConeSize);CHKERRQ(ierr);
126 ierr = DMPlexFixFaceOrientations_Translate_Private(newornts[i], &start0, &reverse0);CHKERRQ(ierr);
127 ierr = DMPlexFixFaceOrientations_Combine_Private(coneConeSize, start0, reverse0, 1, PETSC_FALSE, &start, &reverse);CHKERRQ(ierr);
128 ierr = DMPlexFixFaceOrientations_TranslateBack_Private(coneConeSize, start, reverse, &newornts[i]);CHKERRQ(ierr);
129 }
130 }
131 ierr = DMPlexSetConeOrientation(dm, p, newornts);CHKERRQ(ierr);
132 /* fix oriention of p within cones of p's support points */
133 ierr = DMPlexGetSupport(dm, p, &support);CHKERRQ(ierr);
134 ierr = DMPlexGetSupportSize(dm, p, &supportSize);CHKERRQ(ierr);
135 for (j=0; j<supportSize; j++) {
136 ierr = DMPlexGetCone(dm, support[j], &supportCone);CHKERRQ(ierr);
137 ierr = DMPlexGetConeSize(dm, support[j], &supportConeSize);CHKERRQ(ierr);
138 ierr = DMPlexGetConeOrientation(dm, support[j], &ornts);CHKERRQ(ierr);
139 for (k=0; k<supportConeSize; k++) {
140 if (supportCone[k] != p) continue;
141 ierr = DMPlexFixFaceOrientations_Translate_Private(ornts[k], &start0, &reverse0);CHKERRQ(ierr);
142 ierr = DMPlexFixFaceOrientations_Combine_Private(coneSize, start0, reverse0, start1, reverse1, &start, &reverse);CHKERRQ(ierr);
143 ierr = DMPlexFixFaceOrientations_TranslateBack_Private(coneSize, start, reverse, &newornt);CHKERRQ(ierr);
144 ierr = DMPlexInsertConeOrientation(dm, support[j], k, newornt);CHKERRQ(ierr);
145 }
146 }
147 /* rewrite cone */
148 ierr = DMPlexSetCone(dm, p, newcone);CHKERRQ(ierr);
149 ierr = DMRestoreWorkArray(dm, maxConeSize, MPIU_INT, &newcone);CHKERRQ(ierr);
150 ierr = DMRestoreWorkArray(dm, maxConeSize, MPIU_INT, &newornts);CHKERRQ(ierr);
151 PetscFunctionReturn(0);
152 }
153
154 /*@
155 DMPlexReverseCell - Give a mesh cell the opposite orientation
156
157 Input Parameters:
158 + dm - The DM
159 - cell - The cell number
160
161 Note: The modification of the DM is done in-place.
162
163 Level: advanced
164
165 .seealso: DMPlexOrient(), DMCreate(), DMPLEX
166 @*/
DMPlexReverseCell(DM dm,PetscInt cell)167 PetscErrorCode DMPlexReverseCell(DM dm, PetscInt cell)
168 {
169 /* Note that the reverse orientation ro of a face with orientation o is:
170
171 ro = o >= 0 ? -(faceSize - o) : faceSize + o
172
173 where faceSize is the size of the cone for the face.
174 */
175 const PetscInt *cone, *coneO, *support;
176 PetscInt *revcone, *revconeO;
177 PetscInt maxConeSize, coneSize, supportSize, faceSize, cp, sp;
178 PetscErrorCode ierr;
179
180 PetscFunctionBegin;
181 ierr = DMPlexGetMaxSizes(dm, &maxConeSize, NULL);CHKERRQ(ierr);
182 ierr = DMGetWorkArray(dm, maxConeSize, MPIU_INT, &revcone);CHKERRQ(ierr);
183 ierr = DMGetWorkArray(dm, maxConeSize, MPIU_INT, &revconeO);CHKERRQ(ierr);
184 /* Reverse cone, and reverse orientations of faces */
185 ierr = DMPlexGetConeSize(dm, cell, &coneSize);CHKERRQ(ierr);
186 ierr = DMPlexGetCone(dm, cell, &cone);CHKERRQ(ierr);
187 ierr = DMPlexGetConeOrientation(dm, cell, &coneO);CHKERRQ(ierr);
188 for (cp = 0; cp < coneSize; ++cp) {
189 const PetscInt rcp = coneSize-cp-1;
190
191 ierr = DMPlexGetConeSize(dm, cone[rcp], &faceSize);CHKERRQ(ierr);
192 revcone[cp] = cone[rcp];
193 revconeO[cp] = coneO[rcp] >= 0 ? -(faceSize-coneO[rcp]) : faceSize+coneO[rcp];
194 }
195 ierr = DMPlexSetCone(dm, cell, revcone);CHKERRQ(ierr);
196 ierr = DMPlexSetConeOrientation(dm, cell, revconeO);CHKERRQ(ierr);
197 /* Reverse orientation of this cell in the support hypercells */
198 faceSize = coneSize;
199 ierr = DMPlexGetSupportSize(dm, cell, &supportSize);CHKERRQ(ierr);
200 ierr = DMPlexGetSupport(dm, cell, &support);CHKERRQ(ierr);
201 for (sp = 0; sp < supportSize; ++sp) {
202 ierr = DMPlexGetConeSize(dm, support[sp], &coneSize);CHKERRQ(ierr);
203 ierr = DMPlexGetCone(dm, support[sp], &cone);CHKERRQ(ierr);
204 ierr = DMPlexGetConeOrientation(dm, support[sp], &coneO);CHKERRQ(ierr);
205 for (cp = 0; cp < coneSize; ++cp) {
206 if (cone[cp] != cell) continue;
207 ierr = DMPlexInsertConeOrientation(dm, support[sp], cp, coneO[cp] >= 0 ? -(faceSize-coneO[cp]) : faceSize+coneO[cp]);CHKERRQ(ierr);
208 }
209 }
210 ierr = DMRestoreWorkArray(dm, maxConeSize, MPIU_INT, &revcone);CHKERRQ(ierr);
211 ierr = DMRestoreWorkArray(dm, maxConeSize, MPIU_INT, &revconeO);CHKERRQ(ierr);
212 PetscFunctionReturn(0);
213 }
214
215 /*
216 - Checks face match
217 - Flips non-matching
218 - Inserts faces of support cells in FIFO
219 */
DMPlexCheckFace_Internal(DM dm,PetscInt * faceFIFO,PetscInt * fTop,PetscInt * fBottom,PetscInt cStart,PetscInt fStart,PetscInt fEnd,PetscBT seenCells,PetscBT flippedCells,PetscBT seenFaces)220 static PetscErrorCode DMPlexCheckFace_Internal(DM dm, PetscInt *faceFIFO, PetscInt *fTop, PetscInt *fBottom, PetscInt cStart, PetscInt fStart, PetscInt fEnd, PetscBT seenCells, PetscBT flippedCells, PetscBT seenFaces)
221 {
222 const PetscInt *support, *coneA, *coneB, *coneOA, *coneOB;
223 PetscInt supportSize, coneSizeA, coneSizeB, posA = -1, posB = -1;
224 PetscInt face, dim, seenA, flippedA, seenB, flippedB, mismatch, c;
225 PetscErrorCode ierr;
226
227 PetscFunctionBegin;
228 face = faceFIFO[(*fTop)++];
229 ierr = DMGetDimension(dm, &dim);CHKERRQ(ierr);
230 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr);
231 ierr = DMPlexGetSupport(dm, face, &support);CHKERRQ(ierr);
232 if (supportSize < 2) PetscFunctionReturn(0);
233 if (supportSize != 2) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Faces should separate only two cells, not %d", supportSize);
234 seenA = PetscBTLookup(seenCells, support[0]-cStart);
235 flippedA = PetscBTLookup(flippedCells, support[0]-cStart) ? 1 : 0;
236 seenB = PetscBTLookup(seenCells, support[1]-cStart);
237 flippedB = PetscBTLookup(flippedCells, support[1]-cStart) ? 1 : 0;
238
239 ierr = DMPlexGetConeSize(dm, support[0], &coneSizeA);CHKERRQ(ierr);
240 ierr = DMPlexGetConeSize(dm, support[1], &coneSizeB);CHKERRQ(ierr);
241 ierr = DMPlexGetCone(dm, support[0], &coneA);CHKERRQ(ierr);
242 ierr = DMPlexGetCone(dm, support[1], &coneB);CHKERRQ(ierr);
243 ierr = DMPlexGetConeOrientation(dm, support[0], &coneOA);CHKERRQ(ierr);
244 ierr = DMPlexGetConeOrientation(dm, support[1], &coneOB);CHKERRQ(ierr);
245 for (c = 0; c < coneSizeA; ++c) {
246 if (!PetscBTLookup(seenFaces, coneA[c]-fStart)) {
247 faceFIFO[(*fBottom)++] = coneA[c];
248 ierr = PetscBTSet(seenFaces, coneA[c]-fStart);CHKERRQ(ierr);
249 }
250 if (coneA[c] == face) posA = c;
251 if (*fBottom > fEnd-fStart) SETERRQ3(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %d was pushed exceeding capacity %d > %d", coneA[c], *fBottom, fEnd-fStart);
252 }
253 if (posA < 0) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %d could not be located in cell %d", face, support[0]);
254 for (c = 0; c < coneSizeB; ++c) {
255 if (!PetscBTLookup(seenFaces, coneB[c]-fStart)) {
256 faceFIFO[(*fBottom)++] = coneB[c];
257 ierr = PetscBTSet(seenFaces, coneB[c]-fStart);CHKERRQ(ierr);
258 }
259 if (coneB[c] == face) posB = c;
260 if (*fBottom > fEnd-fStart) SETERRQ3(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Face %d was pushed exceeding capacity %d > %d", coneA[c], *fBottom, fEnd-fStart);
261 }
262 if (posB < 0) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Face %d could not be located in cell %d", face, support[1]);
263
264 if (dim == 1) {
265 mismatch = posA == posB;
266 } else {
267 mismatch = coneOA[posA] == coneOB[posB];
268 }
269
270 if (mismatch ^ (flippedA ^ flippedB)) {
271 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]);
272 if (!seenA && !flippedA) {
273 ierr = PetscBTSet(flippedCells, support[0]-cStart);CHKERRQ(ierr);
274 } else if (!seenB && !flippedB) {
275 ierr = PetscBTSet(flippedCells, support[1]-cStart);CHKERRQ(ierr);
276 } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
277 } else if (mismatch && flippedA && flippedB) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
278 ierr = PetscBTSet(seenCells, support[0]-cStart);CHKERRQ(ierr);
279 ierr = PetscBTSet(seenCells, support[1]-cStart);CHKERRQ(ierr);
280 PetscFunctionReturn(0);
281 }
282
283 /*@
284 DMPlexOrient - Give a consistent orientation to the input mesh
285
286 Input Parameters:
287 . dm - The DM
288
289 Note: The orientation data for the DM are change in-place.
290 $ This routine will fail for non-orientable surfaces, such as the Moebius strip.
291
292 Level: advanced
293
294 .seealso: DMCreate(), DMPLEX
295 @*/
DMPlexOrient(DM dm)296 PetscErrorCode DMPlexOrient(DM dm)
297 {
298 MPI_Comm comm;
299 PetscSF sf;
300 const PetscInt *lpoints;
301 const PetscSFNode *rpoints;
302 PetscSFNode *rorntComp = NULL, *lorntComp = NULL;
303 PetscInt *numNeighbors, **neighbors;
304 PetscSFNode *nrankComp;
305 PetscBool *match, *flipped;
306 PetscBT seenCells, flippedCells, seenFaces;
307 PetscInt *faceFIFO, fTop, fBottom, *cellComp, *faceComp;
308 PetscInt numLeaves, numRoots, dim, h, cStart, cEnd, c, cell, fStart, fEnd, face, off, totNeighbors = 0;
309 PetscMPIInt rank, size, numComponents, comp = 0;
310 PetscBool flg, flg2;
311 PetscViewer viewer = NULL, selfviewer = NULL;
312 PetscErrorCode ierr;
313
314 PetscFunctionBegin;
315 ierr = PetscObjectGetComm((PetscObject) dm, &comm);CHKERRQ(ierr);
316 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr);
317 ierr = MPI_Comm_size(comm, &size);CHKERRQ(ierr);
318 ierr = PetscOptionsHasName(((PetscObject) dm)->options,((PetscObject) dm)->prefix, "-orientation_view", &flg);CHKERRQ(ierr);
319 ierr = PetscOptionsHasName(((PetscObject) dm)->options,((PetscObject) dm)->prefix, "-orientation_view_synchronized", &flg2);CHKERRQ(ierr);
320 ierr = DMGetPointSF(dm, &sf);CHKERRQ(ierr);
321 ierr = PetscSFGetGraph(sf, &numRoots, &numLeaves, &lpoints, &rpoints);CHKERRQ(ierr);
322 /* Truth Table
323 mismatch flips do action mismatch flipA ^ flipB action
324 F 0 flips no F F F
325 F 1 flip yes F T T
326 F 2 flips no T F T
327 T 0 flips yes T T F
328 T 1 flip no
329 T 2 flips yes
330 */
331 ierr = DMGetDimension(dm, &dim);CHKERRQ(ierr);
332 ierr = DMPlexGetVTKCellHeight(dm, &h);CHKERRQ(ierr);
333 ierr = DMPlexGetHeightStratum(dm, h, &cStart, &cEnd);CHKERRQ(ierr);
334 ierr = DMPlexGetHeightStratum(dm, h+1, &fStart, &fEnd);CHKERRQ(ierr);
335 ierr = PetscBTCreate(cEnd - cStart, &seenCells);CHKERRQ(ierr);
336 ierr = PetscBTMemzero(cEnd - cStart, seenCells);CHKERRQ(ierr);
337 ierr = PetscBTCreate(cEnd - cStart, &flippedCells);CHKERRQ(ierr);
338 ierr = PetscBTMemzero(cEnd - cStart, flippedCells);CHKERRQ(ierr);
339 ierr = PetscBTCreate(fEnd - fStart, &seenFaces);CHKERRQ(ierr);
340 ierr = PetscBTMemzero(fEnd - fStart, seenFaces);CHKERRQ(ierr);
341 ierr = PetscCalloc3(fEnd - fStart, &faceFIFO, cEnd-cStart, &cellComp, fEnd-fStart, &faceComp);CHKERRQ(ierr);
342 /*
343 OLD STYLE
344 - Add an integer array over cells and faces (component) for connected component number
345 Foreach component
346 - Mark the initial cell as seen
347 - Process component as usual
348 - Set component for all seenCells
349 - Wipe seenCells and seenFaces (flippedCells can stay)
350 - Generate parallel adjacency for component using SF and seenFaces
351 - Collect numComponents adj data from each proc to 0
352 - Build same serial graph
353 - Use same solver
354 - Use Scatterv to to send back flipped flags for each component
355 - Negate flippedCells by component
356
357 NEW STYLE
358 - Create the adj on each process
359 - Bootstrap to complete graph on proc 0
360 */
361 /* Loop over components */
362 for (cell = cStart; cell < cEnd; ++cell) cellComp[cell-cStart] = -1;
363 do {
364 /* Look for first unmarked cell */
365 for (cell = cStart; cell < cEnd; ++cell) if (cellComp[cell-cStart] < 0) break;
366 if (cell >= cEnd) break;
367 /* Initialize FIFO with first cell in component */
368 {
369 const PetscInt *cone;
370 PetscInt coneSize;
371
372 fTop = fBottom = 0;
373 ierr = DMPlexGetConeSize(dm, cell, &coneSize);CHKERRQ(ierr);
374 ierr = DMPlexGetCone(dm, cell, &cone);CHKERRQ(ierr);
375 for (c = 0; c < coneSize; ++c) {
376 faceFIFO[fBottom++] = cone[c];
377 ierr = PetscBTSet(seenFaces, cone[c]-fStart);CHKERRQ(ierr);
378 }
379 ierr = PetscBTSet(seenCells, cell-cStart);CHKERRQ(ierr);
380 }
381 /* Consider each face in FIFO */
382 while (fTop < fBottom) {
383 ierr = DMPlexCheckFace_Internal(dm, faceFIFO, &fTop, &fBottom, cStart, fStart, fEnd, seenCells, flippedCells, seenFaces);CHKERRQ(ierr);
384 }
385 /* Set component for cells and faces */
386 for (cell = 0; cell < cEnd-cStart; ++cell) {
387 if (PetscBTLookup(seenCells, cell)) cellComp[cell] = comp;
388 }
389 for (face = 0; face < fEnd-fStart; ++face) {
390 if (PetscBTLookup(seenFaces, face)) faceComp[face] = comp;
391 }
392 /* Wipe seenCells and seenFaces for next component */
393 ierr = PetscBTMemzero(fEnd - fStart, seenFaces);CHKERRQ(ierr);
394 ierr = PetscBTMemzero(cEnd - cStart, seenCells);CHKERRQ(ierr);
395 ++comp;
396 } while (1);
397 numComponents = comp;
398 if (flg) {
399 PetscViewer v;
400
401 ierr = PetscViewerASCIIGetStdout(comm, &v);CHKERRQ(ierr);
402 ierr = PetscViewerASCIIPushSynchronized(v);CHKERRQ(ierr);
403 ierr = PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for serial flipped cells:\n", rank);CHKERRQ(ierr);
404 ierr = PetscBTView(cEnd-cStart, flippedCells, v);CHKERRQ(ierr);
405 ierr = PetscViewerFlush(v);CHKERRQ(ierr);
406 ierr = PetscViewerASCIIPopSynchronized(v);CHKERRQ(ierr);
407 }
408 /* Now all subdomains are oriented, but we need a consistent parallel orientation */
409 if (numLeaves >= 0) {
410 /* Store orientations of boundary faces*/
411 ierr = PetscCalloc2(numRoots,&rorntComp,numRoots,&lorntComp);CHKERRQ(ierr);
412 for (face = fStart; face < fEnd; ++face) {
413 const PetscInt *cone, *support, *ornt;
414 PetscInt coneSize, supportSize;
415
416 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr);
417 if (supportSize != 1) continue;
418 ierr = DMPlexGetSupport(dm, face, &support);CHKERRQ(ierr);
419
420 ierr = DMPlexGetCone(dm, support[0], &cone);CHKERRQ(ierr);
421 ierr = DMPlexGetConeSize(dm, support[0], &coneSize);CHKERRQ(ierr);
422 ierr = DMPlexGetConeOrientation(dm, support[0], &ornt);CHKERRQ(ierr);
423 for (c = 0; c < coneSize; ++c) if (cone[c] == face) break;
424 if (dim == 1) {
425 /* Use cone position instead, shifted to -1 or 1 */
426 if (PetscBTLookup(flippedCells, support[0]-cStart)) rorntComp[face].rank = 1-c*2;
427 else rorntComp[face].rank = c*2-1;
428 } else {
429 if (PetscBTLookup(flippedCells, support[0]-cStart)) rorntComp[face].rank = ornt[c] < 0 ? -1 : 1;
430 else rorntComp[face].rank = ornt[c] < 0 ? 1 : -1;
431 }
432 rorntComp[face].index = faceComp[face-fStart];
433 }
434 /* Communicate boundary edge orientations */
435 ierr = PetscSFBcastBegin(sf, MPIU_2INT, rorntComp, lorntComp);CHKERRQ(ierr);
436 ierr = PetscSFBcastEnd(sf, MPIU_2INT, rorntComp, lorntComp);CHKERRQ(ierr);
437 }
438 /* Get process adjacency */
439 ierr = PetscMalloc2(numComponents, &numNeighbors, numComponents, &neighbors);CHKERRQ(ierr);
440 viewer = PETSC_VIEWER_STDOUT_(PetscObjectComm((PetscObject)dm));
441 if (flg2) {ierr = PetscViewerASCIIPushSynchronized(viewer);CHKERRQ(ierr);}
442 ierr = PetscViewerGetSubViewer(viewer,PETSC_COMM_SELF,&selfviewer);CHKERRQ(ierr);
443 for (comp = 0; comp < numComponents; ++comp) {
444 PetscInt l, n;
445
446 numNeighbors[comp] = 0;
447 ierr = PetscMalloc1(PetscMax(numLeaves, 0), &neighbors[comp]);CHKERRQ(ierr);
448 /* I know this is p^2 time in general, but for bounded degree its alright */
449 for (l = 0; l < numLeaves; ++l) {
450 const PetscInt face = lpoints[l];
451
452 /* Find a representative face (edge) separating pairs of procs */
453 if ((face >= fStart) && (face < fEnd) && (faceComp[face-fStart] == comp)) {
454 const PetscInt rrank = rpoints[l].rank;
455 const PetscInt rcomp = lorntComp[face].index;
456
457 for (n = 0; n < numNeighbors[comp]; ++n) if ((rrank == rpoints[neighbors[comp][n]].rank) && (rcomp == lorntComp[lpoints[neighbors[comp][n]]].index)) break;
458 if (n >= numNeighbors[comp]) {
459 PetscInt supportSize;
460
461 ierr = DMPlexGetSupportSize(dm, face, &supportSize);CHKERRQ(ierr);
462 if (supportSize != 1) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Boundary faces should see one cell, not %d", supportSize);
463 if (flg) {ierr = PetscViewerASCIIPrintf(selfviewer, "[%d]: component %d, Found representative leaf %d (face %d) connecting to face %d on (%d, %d) with orientation %d\n", rank, comp, l, face, rpoints[l].index, rrank, rcomp, lorntComp[face].rank);CHKERRQ(ierr);}
464 neighbors[comp][numNeighbors[comp]++] = l;
465 }
466 }
467 }
468 totNeighbors += numNeighbors[comp];
469 }
470 ierr = PetscViewerRestoreSubViewer(viewer,PETSC_COMM_SELF,&selfviewer);CHKERRQ(ierr);
471 ierr = PetscViewerFlush(viewer);CHKERRQ(ierr);
472 if (flg2) {ierr = PetscViewerASCIIPopSynchronized(viewer);CHKERRQ(ierr);}
473 ierr = PetscMalloc2(totNeighbors, &nrankComp, totNeighbors, &match);CHKERRQ(ierr);
474 for (comp = 0, off = 0; comp < numComponents; ++comp) {
475 PetscInt n;
476
477 for (n = 0; n < numNeighbors[comp]; ++n, ++off) {
478 const PetscInt face = lpoints[neighbors[comp][n]];
479 const PetscInt o = rorntComp[face].rank*lorntComp[face].rank;
480
481 if (o < 0) match[off] = PETSC_TRUE;
482 else if (o > 0) match[off] = PETSC_FALSE;
483 else SETERRQ5(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Invalid face %d (%d, %d) neighbor: %d comp: %d", face, rorntComp[face], lorntComp[face], neighbors[comp][n], comp);
484 nrankComp[off].rank = rpoints[neighbors[comp][n]].rank;
485 nrankComp[off].index = lorntComp[lpoints[neighbors[comp][n]]].index;
486 }
487 ierr = PetscFree(neighbors[comp]);CHKERRQ(ierr);
488 }
489 /* Collect the graph on 0 */
490 if (numLeaves >= 0) {
491 Mat G;
492 PetscBT seenProcs, flippedProcs;
493 PetscInt *procFIFO, pTop, pBottom;
494 PetscInt *N = NULL, *Noff;
495 PetscSFNode *adj = NULL;
496 PetscBool *val = NULL;
497 PetscMPIInt *recvcounts = NULL, *displs = NULL, *Nc, p, o;
498 PetscMPIInt size = 0;
499
500 ierr = PetscCalloc1(numComponents, &flipped);CHKERRQ(ierr);
501 if (!rank) {ierr = MPI_Comm_size(comm, &size);CHKERRQ(ierr);}
502 ierr = PetscCalloc4(size, &recvcounts, size+1, &displs, size, &Nc, size+1, &Noff);CHKERRQ(ierr);
503 ierr = MPI_Gather(&numComponents, 1, MPI_INT, Nc, 1, MPI_INT, 0, comm);CHKERRQ(ierr);
504 for (p = 0; p < size; ++p) {
505 displs[p+1] = displs[p] + Nc[p];
506 }
507 if (!rank) {ierr = PetscMalloc1(displs[size],&N);CHKERRQ(ierr);}
508 ierr = MPI_Gatherv(numNeighbors, numComponents, MPIU_INT, N, Nc, displs, MPIU_INT, 0, comm);CHKERRQ(ierr);
509 for (p = 0, o = 0; p < size; ++p) {
510 recvcounts[p] = 0;
511 for (c = 0; c < Nc[p]; ++c, ++o) recvcounts[p] += N[o];
512 displs[p+1] = displs[p] + recvcounts[p];
513 }
514 if (!rank) {ierr = PetscMalloc2(displs[size], &adj, displs[size], &val);CHKERRQ(ierr);}
515 ierr = MPI_Gatherv(nrankComp, totNeighbors, MPIU_2INT, adj, recvcounts, displs, MPIU_2INT, 0, comm);CHKERRQ(ierr);
516 ierr = MPI_Gatherv(match, totNeighbors, MPIU_BOOL, val, recvcounts, displs, MPIU_BOOL, 0, comm);CHKERRQ(ierr);
517 ierr = PetscFree2(numNeighbors, neighbors);CHKERRQ(ierr);
518 if (!rank) {
519 for (p = 1; p <= size; ++p) {Noff[p] = Noff[p-1] + Nc[p-1];}
520 if (flg) {
521 PetscInt n;
522
523 for (p = 0, off = 0; p < size; ++p) {
524 for (c = 0; c < Nc[p]; ++c) {
525 ierr = PetscPrintf(PETSC_COMM_SELF, "Proc %d Comp %d:\n", p, c);CHKERRQ(ierr);
526 for (n = 0; n < N[Noff[p]+c]; ++n, ++off) {
527 ierr = PetscPrintf(PETSC_COMM_SELF, " edge (%d, %d) (%d):\n", adj[off].rank, adj[off].index, val[off]);CHKERRQ(ierr);
528 }
529 }
530 }
531 }
532 /* Symmetrize the graph */
533 ierr = MatCreate(PETSC_COMM_SELF, &G);CHKERRQ(ierr);
534 ierr = MatSetSizes(G, Noff[size], Noff[size], Noff[size], Noff[size]);CHKERRQ(ierr);
535 ierr = MatSetUp(G);CHKERRQ(ierr);
536 for (p = 0, off = 0; p < size; ++p) {
537 for (c = 0; c < Nc[p]; ++c) {
538 const PetscInt r = Noff[p]+c;
539 PetscInt n;
540
541 for (n = 0; n < N[r]; ++n, ++off) {
542 const PetscInt q = Noff[adj[off].rank] + adj[off].index;
543 const PetscScalar o = val[off] ? 1.0 : 0.0;
544
545 ierr = MatSetValues(G, 1, &r, 1, &q, &o, INSERT_VALUES);CHKERRQ(ierr);
546 ierr = MatSetValues(G, 1, &q, 1, &r, &o, INSERT_VALUES);CHKERRQ(ierr);
547 }
548 }
549 }
550 ierr = MatAssemblyBegin(G, MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
551 ierr = MatAssemblyEnd(G, MAT_FINAL_ASSEMBLY);CHKERRQ(ierr);
552
553 ierr = PetscBTCreate(Noff[size], &seenProcs);CHKERRQ(ierr);
554 ierr = PetscBTMemzero(Noff[size], seenProcs);CHKERRQ(ierr);
555 ierr = PetscBTCreate(Noff[size], &flippedProcs);CHKERRQ(ierr);
556 ierr = PetscBTMemzero(Noff[size], flippedProcs);CHKERRQ(ierr);
557 ierr = PetscMalloc1(Noff[size], &procFIFO);CHKERRQ(ierr);
558 pTop = pBottom = 0;
559 for (p = 0; p < Noff[size]; ++p) {
560 if (PetscBTLookup(seenProcs, p)) continue;
561 /* Initialize FIFO with next proc */
562 procFIFO[pBottom++] = p;
563 ierr = PetscBTSet(seenProcs, p);CHKERRQ(ierr);
564 /* Consider each proc in FIFO */
565 while (pTop < pBottom) {
566 const PetscScalar *ornt;
567 const PetscInt *neighbors;
568 PetscInt proc, nproc, seen, flippedA, flippedB, mismatch, numNeighbors, n;
569
570 proc = procFIFO[pTop++];
571 flippedA = PetscBTLookup(flippedProcs, proc) ? 1 : 0;
572 ierr = MatGetRow(G, proc, &numNeighbors, &neighbors, &ornt);CHKERRQ(ierr);
573 /* Loop over neighboring procs */
574 for (n = 0; n < numNeighbors; ++n) {
575 nproc = neighbors[n];
576 mismatch = PetscRealPart(ornt[n]) > 0.5 ? 0 : 1;
577 seen = PetscBTLookup(seenProcs, nproc);
578 flippedB = PetscBTLookup(flippedProcs, nproc) ? 1 : 0;
579
580 if (mismatch ^ (flippedA ^ flippedB)) {
581 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);
582 if (!flippedB) {
583 ierr = PetscBTSet(flippedProcs, nproc);CHKERRQ(ierr);
584 } else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Inconsistent mesh orientation: Fault mesh is non-orientable");
585 } else if (mismatch && flippedA && flippedB) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempt to flip already flipped cell: Fault mesh is non-orientable");
586 if (!seen) {
587 procFIFO[pBottom++] = nproc;
588 ierr = PetscBTSet(seenProcs, nproc);CHKERRQ(ierr);
589 }
590 }
591 }
592 }
593 ierr = PetscFree(procFIFO);CHKERRQ(ierr);
594 ierr = MatDestroy(&G);CHKERRQ(ierr);
595 ierr = PetscFree2(adj, val);CHKERRQ(ierr);
596 ierr = PetscBTDestroy(&seenProcs);CHKERRQ(ierr);
597 }
598 /* Scatter flip flags */
599 {
600 PetscBool *flips = NULL;
601
602 if (!rank) {
603 ierr = PetscMalloc1(Noff[size], &flips);CHKERRQ(ierr);
604 for (p = 0; p < Noff[size]; ++p) {
605 flips[p] = PetscBTLookup(flippedProcs, p) ? PETSC_TRUE : PETSC_FALSE;
606 if (flg && flips[p]) {ierr = PetscPrintf(comm, "Flipping Proc+Comp %d:\n", p);CHKERRQ(ierr);}
607 }
608 for (p = 0; p < size; ++p) {
609 displs[p+1] = displs[p] + Nc[p];
610 }
611 }
612 ierr = MPI_Scatterv(flips, Nc, displs, MPIU_BOOL, flipped, numComponents, MPIU_BOOL, 0, comm);CHKERRQ(ierr);
613 ierr = PetscFree(flips);CHKERRQ(ierr);
614 }
615 if (!rank) {ierr = PetscBTDestroy(&flippedProcs);CHKERRQ(ierr);}
616 ierr = PetscFree(N);CHKERRQ(ierr);
617 ierr = PetscFree4(recvcounts, displs, Nc, Noff);CHKERRQ(ierr);
618 ierr = PetscFree2(nrankComp, match);CHKERRQ(ierr);
619
620 /* Decide whether to flip cells in each component */
621 for (c = 0; c < cEnd-cStart; ++c) {if (flipped[cellComp[c]]) {ierr = PetscBTNegate(flippedCells, c);CHKERRQ(ierr);}}
622 ierr = PetscFree(flipped);CHKERRQ(ierr);
623 }
624 if (flg) {
625 PetscViewer v;
626
627 ierr = PetscViewerASCIIGetStdout(comm, &v);CHKERRQ(ierr);
628 ierr = PetscViewerASCIIPushSynchronized(v);CHKERRQ(ierr);
629 ierr = PetscViewerASCIISynchronizedPrintf(v, "[%d]BT for parallel flipped cells:\n", rank);CHKERRQ(ierr);
630 ierr = PetscBTView(cEnd-cStart, flippedCells, v);CHKERRQ(ierr);
631 ierr = PetscViewerFlush(v);CHKERRQ(ierr);
632 ierr = PetscViewerASCIIPopSynchronized(v);CHKERRQ(ierr);
633 }
634 /* Reverse flipped cells in the mesh */
635 for (c = cStart; c < cEnd; ++c) {
636 if (PetscBTLookup(flippedCells, c-cStart)) {
637 ierr = DMPlexReverseCell(dm, c);CHKERRQ(ierr);
638 }
639 }
640 ierr = PetscBTDestroy(&seenCells);CHKERRQ(ierr);
641 ierr = PetscBTDestroy(&flippedCells);CHKERRQ(ierr);
642 ierr = PetscBTDestroy(&seenFaces);CHKERRQ(ierr);
643 ierr = PetscFree2(numNeighbors, neighbors);CHKERRQ(ierr);
644 ierr = PetscFree2(rorntComp, lorntComp);CHKERRQ(ierr);
645 ierr = PetscFree3(faceFIFO, cellComp, faceComp);CHKERRQ(ierr);
646 PetscFunctionReturn(0);
647 }
648