Actual source code: greedy.c
petsc-3.6.4 2016-04-12
1: #include <petsc/private/matimpl.h> /*I "petscmat.h" I*/
2: #include <../src/mat/impls/aij/seq/aij.h>
3: #include <../src/mat/impls/aij/mpi/mpiaij.h>
4: #include <petscsf.h>
6: typedef struct {
7: PetscBool symmetric;
8: } MC_Greedy;
12: PetscErrorCode MatColoringDestroy_Greedy(MatColoring mc)
13: {
17: PetscFree(mc->data);
18: return(0);
19: }
23: PETSC_EXTERN PetscErrorCode GreedyColoringLocalDistanceOne_Private(MatColoring mc,PetscReal *wts,PetscInt *lperm,ISColoringValue *colors)
24: {
25: PetscInt i,j,k,s,e,n,no,nd,nd_global,n_global,idx,ncols,maxcolors,masksize,ccol,*mask;
26: PetscErrorCode ierr;
27: Mat m=mc->mat;
28: Mat_MPIAIJ *aij = (Mat_MPIAIJ*)m->data;
29: Mat md=NULL,mo=NULL;
30: const PetscInt *md_i,*mo_i,*md_j,*mo_j;
31: PetscBool isMPIAIJ,isSEQAIJ;
32: ISColoringValue pcol;
33: const PetscInt *cidx;
34: PetscInt *lcolors,*ocolors;
35: PetscReal *owts=NULL;
36: PetscSF sf;
37: PetscLayout layout;
40: MatGetSize(m,&n_global,NULL);
41: MatGetOwnershipRange(m,&s,&e);
42: n=e-s;
43: masksize=20;
44: nd_global = 0;
45: /* get the matrix communication structures */
46: PetscObjectTypeCompare((PetscObject)m, MATMPIAIJ, &isMPIAIJ);
47: PetscObjectTypeCompare((PetscObject)m, MATSEQAIJ, &isSEQAIJ);
48: if (isMPIAIJ) {
49: /* get the CSR data for on and off diagonal portions of m */
50: Mat_SeqAIJ *dseq;
51: Mat_SeqAIJ *oseq;
52: md=aij->A;
53: dseq = (Mat_SeqAIJ*)md->data;
54: mo=aij->B;
55: oseq = (Mat_SeqAIJ*)mo->data;
56: md_i = dseq->i;
57: md_j = dseq->j;
58: mo_i = oseq->i;
59: mo_j = oseq->j;
60: } else if (isSEQAIJ) {
61: /* get the CSR data for m */
62: Mat_SeqAIJ *dseq;
63: /* no off-processor nodes */
64: md=m;
65: dseq = (Mat_SeqAIJ*)md->data;
66: mo=NULL;
67: no=0;
68: md_i = dseq->i;
69: md_j = dseq->j;
70: mo_i = NULL;
71: mo_j = NULL;
72: } else {
73: SETERRQ(PetscObjectComm((PetscObject)mc),PETSC_ERR_ARG_WRONG,"Matrix must be AIJ for greedy coloring");
74: }
75: MatColoringGetMaxColors(mc,&maxcolors);
76: if (mo) {
77: VecGetSize(aij->lvec,&no);
78: PetscMalloc2(no,&ocolors,no,&owts);
79: for(i=0;i<no;i++) {
80: ocolors[i]=maxcolors;
81: }
82: }
84: PetscMalloc1(masksize,&mask);
85: PetscMalloc1(n,&lcolors);
86: for(i=0;i<n;i++) {
87: lcolors[i]=maxcolors;
88: }
89: for (i=0;i<masksize;i++) {
90: mask[i]=-1;
91: }
92: if (mo) {
93: /* transfer neighbor weights */
94: PetscSFCreate(PetscObjectComm((PetscObject)m),&sf);
95: MatGetLayouts(m,&layout,NULL);
96: PetscSFSetGraphLayout(sf,layout,no,NULL,PETSC_COPY_VALUES,aij->garray);
97: PetscSFBcastBegin(sf,MPIU_REAL,wts,owts);
98: PetscSFBcastEnd(sf,MPIU_REAL,wts,owts);
99: }
100: while (nd_global < n_global) {
101: nd=n;
102: /* assign lowest possible color to each local vertex */
103: PetscLogEventBegin(Mat_Coloring_Local,mc,0,0,0);
104: for (i=0;i<n;i++) {
105: idx=lperm[i];
106: if (lcolors[idx] == maxcolors) {
107: ncols = md_i[idx+1]-md_i[idx];
108: cidx = &(md_j[md_i[idx]]);
109: for (j=0;j<ncols;j++) {
110: if (lcolors[cidx[j]] != maxcolors) {
111: ccol=lcolors[cidx[j]];
112: if (ccol>=masksize) {
113: PetscInt *newmask;
114: PetscMalloc1(masksize*2,&newmask);
115: for(k=0;k<2*masksize;k++) {
116: newmask[k]=-1;
117: }
118: for(k=0;k<masksize;k++) {
119: newmask[k]=mask[k];
120: }
121: PetscFree(mask);
122: mask=newmask;
123: masksize*=2;
124: }
125: mask[ccol]=idx;
126: }
127: }
128: if (mo) {
129: ncols = mo_i[idx+1]-mo_i[idx];
130: cidx = &(mo_j[mo_i[idx]]);
131: for (j=0;j<ncols;j++) {
132: if (ocolors[cidx[j]] != maxcolors) {
133: ccol=ocolors[cidx[j]];
134: if (ccol>=masksize) {
135: PetscInt *newmask;
136: PetscMalloc1(masksize*2,&newmask);
137: for(k=0;k<2*masksize;k++) {
138: newmask[k]=-1;
139: }
140: for(k=0;k<masksize;k++) {
141: newmask[k]=mask[k];
142: }
143: PetscFree(mask);
144: mask=newmask;
145: masksize*=2;
146: }
147: mask[ccol]=idx;
148: }
149: }
150: }
151: for (j=0;j<masksize;j++) {
152: if (mask[j]!=idx) {
153: break;
154: }
155: }
156: pcol=j;
157: if (pcol>maxcolors)pcol=maxcolors;
158: lcolors[idx]=pcol;
159: }
160: }
161: PetscLogEventEnd(Mat_Coloring_Local,mc,0,0,0);
162: if (mo) {
163: /* transfer neighbor colors */
164: PetscLogEventBegin(Mat_Coloring_Comm,mc,0,0,0);
165: PetscSFBcastBegin(sf,MPIU_INT,lcolors,ocolors);
166: PetscSFBcastEnd(sf,MPIU_INT,lcolors,ocolors);
167: /* check for conflicts -- this is merely checking if any adjacent off-processor rows have the same color and marking the ones that are lower weight locally for changing */
168: for (i=0;i<n;i++) {
169: ncols = mo_i[i+1]-mo_i[i];
170: cidx = &(mo_j[mo_i[i]]);
171: for (j=0;j<ncols;j++) {
172: /* in the case of conflicts, the highest weight one stays and the others go */
173: if ((ocolors[cidx[j]] == lcolors[i]) && (owts[cidx[j]] > wts[i]) && lcolors[i] < maxcolors) {
174: lcolors[i]=maxcolors;
175: nd--;
176: }
177: }
178: }
179: nd_global=0;
180: }
181: MPI_Allreduce(&nd,&nd_global,1,MPIU_INT,MPI_SUM,PetscObjectComm((PetscObject)mc));
182: }
183: for (i=0;i<n;i++) {
184: colors[i] = (ISColoringValue)lcolors[i];
185: }
186: PetscFree(mask);
187: PetscFree(lcolors);
188: if (mo) {
189: PetscFree2(ocolors,owts);
190: PetscSFDestroy(&sf);
191: }
192: return(0);
193: }
199: PETSC_EXTERN PetscErrorCode GreedyColoringLocalDistanceTwo_Private(MatColoring mc,PetscReal *wts,PetscInt *lperm,ISColoringValue *colors)
200: {
201: MC_Greedy *gr = (MC_Greedy *) mc->data;
202: PetscInt i,j,k,l,s,e,n,nd,nd_global,n_global,idx,ncols,maxcolors,mcol,mcol_global,nd1cols,*mask,masksize,*d1cols,*bad,*badnext,nbad,badsize,ccol,no,cbad;
203: Mat m = mc->mat, mt;
204: Mat_MPIAIJ *aij = (Mat_MPIAIJ*)m->data;
205: Mat md=NULL,mo=NULL;
206: const PetscInt *md_i,*mo_i,*md_j,*mo_j;
207: const PetscInt *rmd_i,*rmo_i,*rmd_j,*rmo_j;
208: PetscBool isMPIAIJ,isSEQAIJ;
209: PetscInt pcol,*dcolors,*ocolors;
210: ISColoringValue *badidx;
211: const PetscInt *cidx;
212: PetscReal *owts,*colorweights;
213: PetscInt *oconf,*conf;
214: PetscSF sf;
215: PetscLayout layout;
216: PetscErrorCode ierr;
219: MatGetSize(m,&n_global,NULL);
220: MatGetOwnershipRange(m,&s,&e);
221: n=e-s;
222: nd_global = 0;
223: /* get the matrix communication structures */
224: PetscObjectTypeCompare((PetscObject)m, MATMPIAIJ, &isMPIAIJ);
225: PetscObjectTypeCompare((PetscObject)m, MATSEQAIJ, &isSEQAIJ);
226: if (isMPIAIJ) {
227: Mat_SeqAIJ *dseq;
228: Mat_SeqAIJ *oseq;
229: md=aij->A;
230: dseq = (Mat_SeqAIJ*)md->data;
231: mo=aij->B;
232: oseq = (Mat_SeqAIJ*)mo->data;
233: md_i = dseq->i;
234: md_j = dseq->j;
235: mo_i = oseq->i;
236: mo_j = oseq->j;
237: rmd_i = dseq->i;
238: rmd_j = dseq->j;
239: rmo_i = oseq->i;
240: rmo_j = oseq->j;
241: } else if (isSEQAIJ) {
242: Mat_SeqAIJ *dseq;
243: /* no off-processor nodes */
244: md=m;
245: dseq = (Mat_SeqAIJ*)md->data;
246: md_i = dseq->i;
247: md_j = dseq->j;
248: mo_i = NULL;
249: mo_j = NULL;
250: rmd_i = dseq->i;
251: rmd_j = dseq->j;
252: rmo_i = NULL;
253: rmo_j = NULL;
254: } else {
255: SETERRQ(PetscObjectComm((PetscObject)mc),PETSC_ERR_ARG_WRONG,"Matrix must be AIJ for greedy coloring");
256: }
257: if (!gr->symmetric) {
258: MatTranspose(m, MAT_INITIAL_MATRIX, &mt);
259: if (isSEQAIJ) {
260: Mat_SeqAIJ *dseq = (Mat_SeqAIJ*) mt->data;
261: rmd_i = dseq->i;
262: rmd_j = dseq->j;
263: rmo_i = NULL;
264: rmo_j = NULL;
265: } else SETERRQ(PetscObjectComm((PetscObject) mc), PETSC_ERR_SUP, "Nonsymmetric greedy coloring only works in serial");
266: }
267: /* create the vectors and communication structures if necessary */
268: no=0;
269: if (mo) {
270: VecGetLocalSize(aij->lvec,&no);
271: PetscSFCreate(PetscObjectComm((PetscObject)m),&sf);
272: MatGetLayouts(m,&layout,NULL);
273: PetscSFSetGraphLayout(sf,layout,no,NULL,PETSC_COPY_VALUES,aij->garray);
274: }
275: MatColoringGetMaxColors(mc,&maxcolors);
276: masksize=n;
277: nbad=0;
278: badsize=n;
279: PetscMalloc1(masksize,&mask);
280: PetscMalloc4(n,&d1cols,n,&dcolors,n,&conf,n,&bad);
281: PetscMalloc2(badsize,&badidx,badsize,&badnext);
282: for(i=0;i<masksize;i++) {
283: mask[i]=-1;
284: }
285: for (i=0;i<n;i++) {
286: dcolors[i]=maxcolors;
287: bad[i]=-1;
288: }
289: for (i=0;i<badsize;i++) {
290: badnext[i]=-1;
291: }
292: if (mo) {
293: PetscMalloc3(no,&owts,no,&oconf,no,&ocolors);
294: PetscSFBcastBegin(sf,MPIU_REAL,wts,owts);
295: PetscSFBcastEnd(sf,MPIU_REAL,wts,owts);
296: for (i=0;i<no;i++) {
297: ocolors[i]=maxcolors;
298: }
299: } else { /* Appease overzealous -Wmaybe-initialized */
300: owts = NULL;
301: oconf = NULL;
302: ocolors = NULL;
303: }
304: mcol=0;
305: while (nd_global < n_global) {
306: nd=n;
307: /* assign lowest possible color to each local vertex */
308: mcol_global=0;
309: PetscLogEventBegin(Mat_Coloring_Local,mc,0,0,0);
310: for (i=0;i<n;i++) {
311: idx=lperm[i];
312: if (dcolors[idx] == maxcolors) {
313: /* entries in bad */
314: cbad=bad[idx];
315: while (cbad>=0) {
316: ccol=badidx[cbad];
317: if (ccol>=masksize) {
318: PetscInt *newmask;
319: PetscMalloc1(masksize*2,&newmask);
320: for(k=0;k<2*masksize;k++) {
321: newmask[k]=-1;
322: }
323: for(k=0;k<masksize;k++) {
324: newmask[k]=mask[k];
325: }
326: PetscFree(mask);
327: mask=newmask;
328: masksize*=2;
329: }
330: mask[ccol]=idx;
331: cbad=badnext[cbad];
332: }
333: /* diagonal distance-one rows */
334: nd1cols=0;
335: ncols = rmd_i[idx+1]-rmd_i[idx];
336: cidx = &(rmd_j[rmd_i[idx]]);
337: for (j=0;j<ncols;j++) {
338: d1cols[nd1cols] = cidx[j];
339: nd1cols++;
340: ccol=dcolors[cidx[j]];
341: if (ccol != maxcolors) {
342: if (ccol>=masksize) {
343: PetscInt *newmask;
344: PetscMalloc1(masksize*2,&newmask);
345: for(k=0;k<2*masksize;k++) {
346: newmask[k]=-1;
347: }
348: for(k=0;k<masksize;k++) {
349: newmask[k]=mask[k];
350: }
351: PetscFree(mask);
352: mask=newmask;
353: masksize*=2;
354: }
355: mask[ccol]=idx;
356: }
357: }
358: /* off-diagonal distance-one rows */
359: if (mo) {
360: ncols = rmo_i[idx+1]-rmo_i[idx];
361: cidx = &(rmo_j[rmo_i[idx]]);
362: for (j=0;j<ncols;j++) {
363: ccol=ocolors[cidx[j]];
364: if (ccol != maxcolors) {
365: if (ccol>=masksize) {
366: PetscInt *newmask;
367: PetscMalloc1(masksize*2,&newmask);
368: for(k=0;k<2*masksize;k++) {
369: newmask[k]=-1;
370: }
371: for(k=0;k<masksize;k++) {
372: newmask[k]=mask[k];
373: }
374: PetscFree(mask);
375: mask=newmask;
376: masksize*=2;
377: }
378: mask[ccol]=idx;
379: }
380: }
381: }
382: /* diagonal distance-two rows */
383: for (j=0;j<nd1cols;j++) {
384: ncols = md_i[d1cols[j]+1]-md_i[d1cols[j]];
385: cidx = &(md_j[md_i[d1cols[j]]]);
386: for (l=0;l<ncols;l++) {
387: ccol=dcolors[cidx[l]];
388: if (ccol != maxcolors) {
389: if (ccol>=masksize) {
390: PetscInt *newmask;
391: PetscMalloc1(masksize*2,&newmask);
392: for(k=0;k<2*masksize;k++) {
393: newmask[k]=-1;
394: }
395: for(k=0;k<masksize;k++) {
396: newmask[k]=mask[k];
397: }
398: PetscFree(mask);
399: mask=newmask;
400: masksize*=2;
401: }
402: mask[ccol]=idx;
403: }
404: }
405: }
406: /* off-diagonal distance-two rows */
407: if (mo) {
408: for (j=0;j<nd1cols;j++) {
409: ncols = mo_i[d1cols[j]+1]-mo_i[d1cols[j]];
410: cidx = &(mo_j[mo_i[d1cols[j]]]);
411: for (l=0;l<ncols;l++) {
412: ccol=ocolors[cidx[l]];
413: if (ccol != maxcolors) {
414: if (ccol>=masksize) {
415: PetscInt *newmask;
416: PetscMalloc1(masksize*2,&newmask);
417: for(k=0;k<2*masksize;k++) {
418: newmask[k]=-1;
419: }
420: for(k=0;k<masksize;k++) {
421: newmask[k]=mask[k];
422: }
423: PetscFree(mask);
424: mask=newmask;
425: masksize*=2;
426: }
427: mask[ccol]=idx;
428: }
429: }
430: }
431: }
432: /* assign this one the lowest color possible by seeing if there's a gap in the sequence of sorted neighbor colors */
433: pcol=0;
434: for (j=0;j<masksize;j++) {
435: if (mask[j]!=idx) {
436: break;
437: }
438: }
439: pcol=j;
440: if (pcol>maxcolors) pcol=maxcolors;
441: dcolors[idx]=pcol;
442: if (pcol>mcol) mcol=pcol;
443: }
444: }
445: PetscLogEventEnd(Mat_Coloring_Local,mc,0,0,0);
446: if (mo) {
447: /* transfer neighbor colors */
448: PetscSFBcastBegin(sf,MPIU_INT,dcolors,ocolors);
449: PetscSFBcastEnd(sf,MPIU_INT,dcolors,ocolors);
450: /* find the maximum color assigned locally and allocate a mask */
451: MPI_Allreduce(&mcol,&mcol_global,1,MPIU_INT,MPI_MAX,PetscObjectComm((PetscObject)mc));
452: PetscMalloc1(mcol_global+1,&colorweights);
453: /* check for conflicts */
454: for (i=0;i<n;i++) {
455: conf[i]=PETSC_FALSE;
456: }
457: for (i=0;i<no;i++) {
458: oconf[i]=PETSC_FALSE;
459: }
460: for (i=0;i<n;i++) {
461: ncols = mo_i[i+1]-mo_i[i];
462: cidx = &(mo_j[mo_i[i]]);
463: if (ncols > 0) {
464: /* fill in the mask */
465: for (j=0;j<mcol_global+1;j++) {
466: colorweights[j]=0;
467: }
468: colorweights[dcolors[i]]=wts[i];
469: /* fill in the off-diagonal part of the mask */
470: for (j=0;j<ncols;j++) {
471: ccol=ocolors[cidx[j]];
472: if (ccol < maxcolors) {
473: if (colorweights[ccol] < owts[cidx[j]]) {
474: colorweights[ccol] = owts[cidx[j]];
475: }
476: }
477: }
478: /* fill in the on-diagonal part of the mask */
479: ncols = md_i[i+1]-md_i[i];
480: cidx = &(md_j[md_i[i]]);
481: for (j=0;j<ncols;j++) {
482: ccol=dcolors[cidx[j]];
483: if (ccol < maxcolors) {
484: if (colorweights[ccol] < wts[cidx[j]]) {
485: colorweights[ccol] = wts[cidx[j]];
486: }
487: }
488: }
489: /* go back through and set up on and off-diagonal conflict vectors */
490: ncols = md_i[i+1]-md_i[i];
491: cidx = &(md_j[md_i[i]]);
492: for (j=0;j<ncols;j++) {
493: ccol=dcolors[cidx[j]];
494: if (ccol < maxcolors) {
495: if (colorweights[ccol] > wts[cidx[j]]) {
496: conf[cidx[j]]=PETSC_TRUE;
497: }
498: }
499: }
500: ncols = mo_i[i+1]-mo_i[i];
501: cidx = &(mo_j[mo_i[i]]);
502: for (j=0;j<ncols;j++) {
503: ccol=ocolors[cidx[j]];
504: if (ccol < maxcolors) {
505: if (colorweights[ccol] > owts[cidx[j]]) {
506: oconf[cidx[j]]=PETSC_TRUE;
507: }
508: }
509: }
510: }
511: }
512: nd_global=0;
513: PetscFree(colorweights);
514: PetscLogEventBegin(Mat_Coloring_Comm,mc,0,0,0);
515: PetscSFReduceBegin(sf,MPIU_INT,oconf,conf,MPIU_SUM);
516: PetscSFReduceEnd(sf,MPIU_INT,oconf,conf,MPIU_SUM);
517: PetscLogEventEnd(Mat_Coloring_Comm,mc,0,0,0);
518: /* go through and unset local colors that have conflicts */
519: for (i=0;i<n;i++) {
520: if (conf[i]>0) {
521: /* push this color onto the bad stack */
522: badidx[nbad]=dcolors[i];
523: badnext[nbad]=bad[i];
524: bad[i]=nbad;
525: nbad++;
526: if (nbad>=badsize) {
527: PetscInt *newbadnext;
528: ISColoringValue *newbadidx;
529: PetscMalloc2(badsize*2,&newbadidx,badsize*2,&newbadnext);
530: for(k=0;k<2*badsize;k++) {
531: newbadnext[k]=-1;
532: }
533: for(k=0;k<badsize;k++) {
534: newbadidx[k]=badidx[k];
535: newbadnext[k]=badnext[k];
536: }
537: PetscFree2(badidx,badnext);
538: badidx=newbadidx;
539: badnext=newbadnext;
540: badsize*=2;
541: }
542: dcolors[i] = maxcolors;
543: nd--;
544: }
545: }
546: }
547: MPI_Allreduce(&nd,&nd_global,1,MPIU_INT,MPI_SUM,PetscObjectComm((PetscObject)mc));
548: }
549: if (mo) {
550: PetscSFDestroy(&sf);
551: PetscFree3(owts,oconf,ocolors);
552: }
553: for (i=0;i<n;i++) {
554: colors[i]=dcolors[i];
555: }
556: PetscFree(mask);
557: PetscFree4(d1cols,dcolors,conf,bad);
558: PetscFree2(badidx,badnext);
559: if (!gr->symmetric) {MatDestroy(&mt);}
560: return(0);
561: }
565: PETSC_EXTERN PetscErrorCode MatColoringApply_Greedy(MatColoring mc,ISColoring *iscoloring)
566: {
567: PetscErrorCode ierr;
568: PetscInt finalcolor,finalcolor_global;
569: ISColoringValue *colors;
570: PetscInt ncolstotal,ncols;
571: PetscReal *wts;
572: PetscInt i,*lperm;
575: MatGetSize(mc->mat,NULL,&ncolstotal);
576: MatGetLocalSize(mc->mat,NULL,&ncols);
577: if (!mc->user_weights) {
578: MatColoringCreateWeights(mc,&wts,&lperm);
579: } else {
580: wts = mc->user_weights;
581: lperm = mc->user_lperm;
582: }
583: PetscMalloc1(ncols,&colors);
584: if (mc->dist == 1) {
585: GreedyColoringLocalDistanceOne_Private(mc,wts,lperm,colors);
586: } else if (mc->dist == 2) {
587: GreedyColoringLocalDistanceTwo_Private(mc,wts,lperm,colors);
588: } else {
589: SETERRQ(PetscObjectComm((PetscObject)mc),PETSC_ERR_ARG_OUTOFRANGE,"Only distance 1 and distance 2 supported by MatColoringGreedy");
590: }
591: finalcolor=0;
592: for (i=0;i<ncols;i++) {
593: if (colors[i] > finalcolor) finalcolor=colors[i];
594: }
595: finalcolor_global=0;
596: MPI_Allreduce(&finalcolor,&finalcolor_global,1,MPIU_INT,MPI_MAX,PetscObjectComm((PetscObject)mc));
597: PetscLogEventBegin(Mat_Coloring_ISCreate,mc,0,0,0);
598: ISColoringCreate(PetscObjectComm((PetscObject)mc),finalcolor_global+1,ncols,colors,PETSC_OWN_POINTER,iscoloring);
599: PetscLogEventEnd(Mat_Coloring_ISCreate,mc,0,0,0);
600: if (!mc->user_weights) {
601: PetscFree(wts);
602: PetscFree(lperm);
603: }
604: return(0);
605: }
609: PetscErrorCode MatColoringSetFromOptions_Greedy(PetscOptions *PetscOptionsObject, MatColoring mc)
610: {
611: MC_Greedy *gr = (MC_Greedy *) mc->data;
615: PetscOptionsHead(PetscOptionsObject, "Greedy options");
616: PetscOptionsBool("-mat_coloring_greedy_symmetric", "Flag for assuming a symmetric matrix", "", gr->symmetric, &gr->symmetric, NULL);
617: PetscOptionsTail();
618: return(0);
619: }
623: /*MC
624: MATCOLORINGGREEDY - Greedy-with-conflict correction based Matrix Coloring for distance 1 and 2.
626: Level: beginner
628: Notes:
630: These algorithms proceed in two phases -- local coloring and conflict resolution. The local coloring
631: tentatively colors all vertices at the distance required given what's known of the global coloring. Then,
632: the updated colors are transferred to different processors at distance one. In the distance one case, each
633: vertex with nonlocal neighbors is then checked to see if it conforms, with the vertex being
634: marked for recoloring if its lower weight than its same colored neighbor. In the distance two case,
635: each boundary vertex's immediate star is checked for validity of the coloring. Lower-weight conflict
636: vertices are marked, and then the conflicts are gathered back on owning processors. In both cases
637: this is done until each column has received a valid color.
639: References:
641: Bozdag et al. "A Parallel Distance-2 Graph Coloring Algorithm for Distributed Memory Computers"
642: HPCC'05 Proceedings of the First international conference on High Performance Computing and Communications
643: Pages 796--806
645: .seealso: MatColoringCreate(), MatColoring, MatColoringSetType()
646: M*/
647: PETSC_EXTERN PetscErrorCode MatColoringCreate_Greedy(MatColoring mc)
648: {
649: MC_Greedy *gr;
653: PetscNewLog(mc,&gr);
654: mc->data = gr;
655: mc->ops->apply = MatColoringApply_Greedy;
656: mc->ops->view = NULL;
657: mc->ops->destroy = MatColoringDestroy_Greedy;
658: mc->ops->setfromoptions = MatColoringSetFromOptions_Greedy;
660: gr->symmetric = PETSC_TRUE;
661: return(0);
662: }