Actual source code: matcoloring.c
petsc-3.13.6 2020-09-29
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: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
29: @*/
30: PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
31: {
35: MatInitializePackage();
36: PetscFunctionListAdd(&MatColoringList,sname,function);
37: return(0);
38: }
40: /*@
41: MatColoringCreate - Creates a matrix coloring context.
43: Collective on MatColoring
45: Input Parameters:
46: . comm - MPI communicator
48: Output Parameter:
49: . mcptr - the new MatColoring context
51: Options Database Keys:
52: + -mat_coloring_type - the type of coloring algorithm used
53: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
54: . -mat_coloring_distance - compute a distance 1,2,... coloring.
55: . -mat_coloring_view - print information about the coloring and the produced index sets
56: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
57: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
59: Level: beginner
61: Notes:
62: 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: Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the MatColoring object or from the mesh from which the
66: matrix comes from with DMCreateColoring(). In general using the mesh produces a more optimal coloring (fewer colors).
68: Some coloring types only support distance two colorings
70: .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate(), DMCreateColoring()
71: @*/
72: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
73: {
74: MatColoring mc;
80: *mcptr = NULL;
82: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
83: MatInitializePackage();
84: #endif
85: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
86: PetscObjectReference((PetscObject)m);
87: mc->mat = m;
88: mc->dist = 2; /* default to Jacobian computation case */
89: mc->maxcolors = IS_COLORING_MAX;
90: *mcptr = mc;
91: mc->valid = PETSC_FALSE;
92: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
93: mc->user_weights = NULL;
94: mc->user_lperm = NULL;
95: return(0);
96: }
99: /*@
100: MatColoringDestroy - Destroys the matrix coloring context
102: Collective on MatColoring
104: Input Parameter:
105: . mc - the MatColoring context
107: Level: beginner
109: .seealso: MatColoringCreate(), MatColoringApply()
110: @*/
111: PetscErrorCode MatColoringDestroy(MatColoring *mc)
112: {
116: if (--((PetscObject)(*mc))->refct > 0) {*mc = 0; return(0);}
117: MatDestroy(&(*mc)->mat);
118: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
119: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
120: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
121: PetscHeaderDestroy(mc);
122: return(0);
123: }
125: /*@C
126: MatColoringSetType - Sets the type of coloring algorithm used
128: Collective on MatColoring
130: Input Parameter:
131: + mc - the MatColoring context
132: - type - the type of coloring
134: Level: beginner
136: Notes:
137: Possible types include the sequential types MATCOLORINGLF,
138: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
139: as a parallel MATCOLORINGMIS algorithm.
141: .seealso: MatColoringCreate(), MatColoringApply()
142: @*/
143: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
144: {
145: PetscBool match;
146: PetscErrorCode ierr,(*r)(MatColoring);
151: PetscObjectTypeCompare((PetscObject)mc,type,&match);
152: if (match) return(0);
153: PetscFunctionListFind(MatColoringList,type,&r);
154: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
155: if (mc->ops->destroy) {
156: (*(mc)->ops->destroy)(mc);
157: mc->ops->destroy = NULL;
158: }
159: mc->ops->apply = 0;
160: mc->ops->view = 0;
161: mc->ops->setfromoptions = 0;
162: mc->ops->destroy = 0;
164: PetscObjectChangeTypeName((PetscObject)mc,type);
165: (*r)(mc);
166: return(0);
167: }
169: /*@
170: MatColoringSetFromOptions - Sets MatColoring options from user parameters
172: Collective on MatColoring
174: Input Parameters:
175: . mc - MatColoring context
177: Options Database Keys:
178: + -mat_coloring_type - the type of coloring algorithm used
179: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
180: . -mat_coloring_distance - compute a distance 1,2,... coloring.
181: . -mat_coloring_view - print information about the coloring and the produced index sets
182: . -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
183: - -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)
185: Level: beginner
187: .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor()
188: @*/
189: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
190: {
191: PetscBool flg;
192: MatColoringType deft = MATCOLORINGSL;
193: char type[256];
195: PetscInt dist,maxcolors;
199: MatColoringGetDistance(mc,&dist);
200: if (dist == 2) deft = MATCOLORINGSL;
201: else deft = MATCOLORINGGREEDY;
202: MatColoringGetMaxColors(mc,&maxcolors);
203: MatColoringRegisterAll();
204: PetscObjectOptionsBegin((PetscObject)mc);
205: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
206: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
207: if (flg) {
208: MatColoringSetType(mc,type);
209: } else if (!((PetscObject)mc)->type_name) {
210: MatColoringSetType(mc,deft);
211: }
212: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
213: if (flg) {MatColoringSetDistance(mc,dist);}
214: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
215: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
216: if (mc->ops->setfromoptions) {
217: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
218: }
219: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
220: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
221: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
222: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
223: PetscOptionsEnd();
224: return(0);
225: }
227: /*@
228: MatColoringSetDistance - Sets the distance of the coloring
230: Logically Collective on MatColoring
232: Input Parameters:
233: + mc - the MatColoring context
234: - dist - the distance the coloring should compute
236: Level: beginner
238: Notes:
239: The distance of the coloring denotes the minimum number
240: of edges in the graph induced by the matrix any two vertices
241: of the same color are. Distance-1 colorings are the classical
242: coloring, where no two vertices of the same color are adjacent.
243: distance-2 colorings are useful for the computation of Jacobians.
245: .seealso: MatColoringGetDistance(), MatColoringApply()
246: @*/
247: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
248: {
251: mc->dist = dist;
252: return(0);
253: }
255: /*@
256: MatColoringGetDistance - Gets the distance of the coloring
258: Logically Collective on MatColoring
260: Input Parameter:
261: . mc - the MatColoring context
263: Output Parameter:
264: . dist - the current distance being used for the coloring.
266: Level: beginner
268: .seealso: MatColoringSetDistance(), MatColoringApply()
269: @*/
270: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
271: {
274: if (dist) *dist = mc->dist;
275: return(0);
276: }
278: /*@
279: MatColoringSetMaxColors - Sets the maximum number of colors
281: Logically Collective on MatColoring
283: Input Parameter:
284: + mc - the MatColoring context
285: - maxcolors - the maximum number of colors to produce
287: Level: beginner
289: Notes:
290: This may be used to compute a certain number of
291: independent sets from the graph. For instance, while using
292: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
293: not in a color are set to have color maxcolors+1, which is not
294: a valid color as they may be adjacent.
296: .seealso: MatColoringGetMaxColors(), MatColoringApply()
297: @*/
298: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
299: {
302: mc->maxcolors = maxcolors;
303: return(0);
304: }
306: /*@
307: MatColoringGetMaxColors - Gets the maximum number of colors
309: Logically Collective on MatColoring
311: Input Parameter:
312: . mc - the MatColoring context
314: Output Parameter:
315: . maxcolors - the current maximum number of colors to produce
317: Level: beginner
319: .seealso: MatColoringSetMaxColors(), MatColoringApply()
320: @*/
321: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
322: {
325: if (maxcolors) *maxcolors = mc->maxcolors;
326: return(0);
327: }
329: /*@
330: MatColoringApply - Apply the coloring to the matrix, producing index
331: sets corresponding to a number of independent sets in the induced
332: graph.
334: Collective on MatColoring
336: Input Parameters:
337: . mc - the MatColoring context
339: Output Parameter:
340: . coloring - the ISColoring instance containing the coloring
342: Level: beginner
344: .seealso: MatColoring, MatColoringCreate()
345: @*/
346: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
347: {
348: PetscErrorCode ierr;
349: PetscBool flg;
350: PetscViewerFormat format;
351: PetscViewer viewer;
352: PetscInt nc,ncolors;
356: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
357: (*mc->ops->apply)(mc,coloring);
358: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
360: /* valid */
361: if (mc->valid) {
362: MatColoringTest(mc,*coloring);
363: }
364: if (mc->valid_iscoloring) {
365: MatISColoringTest(mc->mat,*coloring);
366: }
368: /* view */
369: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
370: if (flg && !PetscPreLoadingOn) {
371: PetscViewerPushFormat(viewer,format);
372: MatColoringView(mc,viewer);
373: MatGetSize(mc->mat,NULL,&nc);
374: ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);
375: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
376: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
377: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
378: PetscViewerPopFormat(viewer);
379: PetscViewerDestroy(&viewer);
380: }
381: return(0);
382: }
384: /*@
385: MatColoringView - Output details about the MatColoring.
387: Collective on MatColoring
389: Input Parameters:
390: - mc - the MatColoring context
391: + viewer - the Viewer context
393: Level: beginner
395: .seealso: MatColoring, MatColoringApply()
396: @*/
397: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
398: {
400: PetscBool iascii;
404: if (!viewer) {
405: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
406: }
410: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
411: if (iascii) {
412: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
413: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
414: if (mc->maxcolors > 0) {
415: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
416: } else {
417: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
418: }
419: }
420: return(0);
421: }
423: /*@
424: MatColoringSetWeightType - Set the type of weight computation used.
426: Logically collective on MatColoring
428: Input Parameters:
429: - mc - the MatColoring context
430: + wt - the weight type
432: Level: beginner
434: .seealso: MatColoring, MatColoringWeightType
435: @*/
436: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
437: {
439: mc->weight_type = wt;
440: return(0);
442: }