Actual source code: matcoloring.c
petsc-3.9.4 2018-09-11
1: #include <petsc/private/matimpl.h>
3: PetscFunctionList MatColoringList = 0;
4: PetscBool MatColoringRegisterAllCalled = PETSC_FALSE;
5: const char *const MatColoringWeightTypes[] = {"RANDOM","LEXICAL","LF","SL","MatColoringWeightType","MAT_COLORING_WEIGHT_",0};
7: /*@C
8: MatColoringRegister - Adds a new sparse matrix coloring to the matrix package.
10: Not Collective
12: Input Parameters:
13: + sname - name of Coloring (for example MATCOLORINGSL)
14: - function - function pointer that creates the coloring
16: Level: developer
18: Sample usage:
19: .vb
20: MatColoringRegister("my_color",MyColor);
21: .ve
23: Then, your partitioner can be chosen with the procedural interface via
24: $ MatColoringSetType(part,"my_color")
25: or at runtime via the option
26: $ -mat_coloring_type my_color
28: .keywords: matrix, Coloring, register
30: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
31: @*/
32: PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
33: {
37: PetscFunctionListAdd(&MatColoringList,sname,function);
38: return(0);
39: }
41: /*@
42: MatColoringCreate - Creates a matrix coloring context.
44: Collective on MatColoring
46: Input Parameters:
47: . comm - MPI communicator
49: Output Parameter:
50: . mcptr - the new MatColoring context
52: Options Database Keys:
53: + -mat_coloring_type - the type of coloring algorithm used
54: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
55: . -mat_coloring_distance - compute a distance 1,2,... coloring.
56: . -mat_coloring_view - print information about the coloring and the produced index sets
57: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
58: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
60: Level: beginner
62: Notes: A distance one coloring is useful, for example, multi-color SOR. A distance two coloring is for the finite difference computation of Jacobians
63: (see MatFDColoringCreate()).
65: Some coloring types only support distance two colorings
67: .keywords: Coloring, Matrix
69: .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate()
70: @*/
71: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
72: {
73: MatColoring mc;
79: *mcptr = NULL;
81: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
82: MatInitializePackage();
83: #endif
84: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
85: PetscObjectReference((PetscObject)m);
86: mc->mat = m;
87: mc->dist = 2; /* default to Jacobian computation case */
88: mc->maxcolors = IS_COLORING_MAX;
89: *mcptr = mc;
90: mc->valid = PETSC_FALSE;
91: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
92: mc->user_weights = NULL;
93: mc->user_lperm = NULL;
94: return(0);
95: }
98: /*@
99: MatColoringDestroy - Destroys the matrix coloring context
101: Collective on MatColoring
103: Input Parameter:
104: . mc - the MatColoring context
106: Level: beginner
108: .keywords: Coloring, destroy
110: .seealso: MatColoringCreate(), MatColoringApply()
111: @*/
112: PetscErrorCode MatColoringDestroy(MatColoring *mc)
113: {
117: if (--((PetscObject)(*mc))->refct > 0) {*mc = 0; return(0);}
118: MatDestroy(&(*mc)->mat);
119: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
120: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
121: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
122: PetscHeaderDestroy(mc);
123: return(0);
124: }
126: /*@C
127: MatColoringSetType - Sets the type of coloring algorithm used
129: Collective on MatColoring
131: Input Parameter:
132: + mc - the MatColoring context
133: - type - the type of coloring
135: Level: beginner
137: Notes: Possible types include the sequential types MATCOLORINGLF,
138: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
139: as a parallel MATCOLORINGMIS algorithm.
141: .keywords: Coloring, type
143: .seealso: MatColoringCreate(), MatColoringApply()
144: @*/
145: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
146: {
147: PetscBool match;
148: PetscErrorCode ierr,(*r)(MatColoring);
153: PetscObjectTypeCompare((PetscObject)mc,type,&match);
154: if (match) return(0);
155: PetscFunctionListFind(MatColoringList,type,&r);
156: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
157: if (mc->ops->destroy) {
158: (*(mc)->ops->destroy)(mc);
159: mc->ops->destroy = NULL;
160: }
161: mc->ops->apply = 0;
162: mc->ops->view = 0;
163: mc->ops->setfromoptions = 0;
164: mc->ops->destroy = 0;
166: PetscObjectChangeTypeName((PetscObject)mc,type);
167: (*r)(mc);
168: return(0);
169: }
171: /*@
172: MatColoringSetFromOptions - Sets MatColoring options from user parameters
174: Collective on MatColoring
176: Input Parameters:
177: . mc - MatColoring context
179: Options Database Keys:
180: + -mat_coloring_type - the type of coloring algorithm used
181: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
182: . -mat_coloring_distance - compute a distance 1,2,... coloring.
183: . -mat_coloring_view - print information about the coloring and the produced index sets
185: Level: beginner
187: .keywords: Coloring, Matrix
189: .seealso: MatColoring, MatColoringApply()
190: @*/
191: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
192: {
193: PetscBool flg;
194: MatColoringType deft = MATCOLORINGSL;
195: char type[256];
197: PetscInt dist,maxcolors;
201: MatColoringGetDistance(mc,&dist);
202: if (dist == 2) deft = MATCOLORINGSL;
203: else deft = MATCOLORINGGREEDY;
204: MatColoringGetMaxColors(mc,&maxcolors);
205: MatColoringRegisterAll();
206: PetscObjectOptionsBegin((PetscObject)mc);
207: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
208: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
209: if (flg) {
210: MatColoringSetType(mc,type);
211: } else if (!((PetscObject)mc)->type_name) {
212: MatColoringSetType(mc,deft);
213: }
214: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
215: if (flg) {MatColoringSetDistance(mc,dist);}
216: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
217: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
218: if (mc->ops->setfromoptions) {
219: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
220: }
221: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
222: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
223: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
224: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
225: PetscOptionsEnd();
226: return(0);
227: }
229: /*@
230: MatColoringSetDistance - Sets the distance of the coloring
232: Logically Collective on MatColoring
234: Input Parameter:
235: . mc - the MatColoring context
236: . dist - the distance the coloring should compute
238: Level: beginner
240: Notes: The distance of the coloring denotes the minimum number
241: of edges in the graph induced by the matrix any two vertices
242: of the same color are. Distance-1 colorings are the classical
243: coloring, where no two vertices of the same color are adjacent.
244: distance-2 colorings are useful for the computation of Jacobians.
246: .keywords: Coloring, distance, Jacobian
248: .seealso: MatColoringGetDistance(), MatColoringApply()
249: @*/
250: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
251: {
254: mc->dist = dist;
255: return(0);
256: }
258: /*@
259: MatColoringGetDistance - Gets the distance of the coloring
261: Logically Collective on MatColoring
263: Input Parameter:
264: . mc - the MatColoring context
266: Output Paramter:
267: . dist - the current distance being used for the coloring.
269: Level: beginner
271: .keywords: Coloring, distance
273: .seealso: MatColoringSetDistance(), MatColoringApply()
274: @*/
275: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
276: {
279: if (dist) *dist = mc->dist;
280: return(0);
281: }
283: /*@
284: MatColoringSetMaxColors - Sets the maximum number of colors
286: Logically Collective on MatColoring
288: Input Parameter:
289: + mc - the MatColoring context
290: - maxcolors - the maximum number of colors to produce
292: Level: beginner
294: Notes: This may be used to compute a certain number of
295: independent sets from the graph. For instance, while using
296: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
297: not in a color are set to have color maxcolors+1, which is not
298: a valid color as they may be adjacent.
300: .keywords: Coloring
302: .seealso: MatColoringGetMaxColors(), MatColoringApply()
303: @*/
304: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
305: {
308: mc->maxcolors = maxcolors;
309: return(0);
310: }
312: /*@
313: MatColoringGetMaxColors - Gets the maximum number of colors
315: Logically Collective on MatColoring
317: Input Parameter:
318: . mc - the MatColoring context
320: Output Paramter:
321: . maxcolors - the current maximum number of colors to produce
323: Level: beginner
325: .keywords: Coloring
327: .seealso: MatColoringSetMaxColors(), MatColoringApply()
328: @*/
329: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
330: {
333: if (maxcolors) *maxcolors = mc->maxcolors;
334: return(0);
335: }
337: /*@
338: MatColoringApply - Apply the coloring to the matrix, producing index
339: sets corresponding to a number of independent sets in the induced
340: graph.
342: Collective on MatColoring
344: Input Parameters:
345: . mc - the MatColoring context
347: Output Parameter:
348: . coloring - the ISColoring instance containing the coloring
350: Level: beginner
352: .keywords: Coloring, Apply
354: .seealso: MatColoring, MatColoringCreate()
355: @*/
356: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
357: {
358: PetscErrorCode ierr;
359: PetscBool flg;
360: PetscViewerFormat format;
361: PetscViewer viewer;
362: PetscInt nc,ncolors;
366: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
367: (*mc->ops->apply)(mc,coloring);
368: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
370: /* valid */
371: if (mc->valid) {
372: MatColoringTest(mc,*coloring);
373: }
374: if (mc->valid_iscoloring) {
375: MatISColoringTest(mc->mat,*coloring);
376: }
378: /* view */
379: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
380: if (flg && !PetscPreLoadingOn) {
381: PetscViewerPushFormat(viewer,format);
382: MatColoringView(mc,viewer);
383: MatGetSize(mc->mat,NULL,&nc);
384: ISColoringGetIS(*coloring,&ncolors,NULL);
385: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
386: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
387: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
388: PetscViewerPopFormat(viewer);
389: PetscViewerDestroy(&viewer);
390: }
391: return(0);
392: }
394: /*@
395: MatColoringView - Output details about the MatColoring.
397: Collective on MatColoring
399: Input Parameters:
400: - mc - the MatColoring context
401: + viewer - the Viewer context
403: Level: beginner
405: .keywords: Coloring, view
407: .seealso: MatColoring, MatColoringApply()
408: @*/
409: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
410: {
412: PetscBool iascii;
416: if (!viewer) {
417: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
418: }
422: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
423: if (iascii) {
424: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
425: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
426: if (mc->maxcolors > 0) {
427: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
428: } else {
429: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
430: }
431: }
432: return(0);
433: }
435: /*@
436: MatColoringSetWeightType - Set the type of weight computation used.
438: Logically collective on MatColoring
440: Input Parameters:
441: - mc - the MatColoring context
442: + wt - the weight type
444: Level: beginner
446: .keywords: Coloring, view
448: .seealso: MatColoring, MatColoringWeightType
449: @*/
450: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
451: {
453: mc->weight_type = wt;
454: return(0);
456: }