Actual source code: matcoloring.c
1: #include <petsc/private/matimpl.h>
3: PetscFunctionList MatColoringList = NULL;
4: PetscBool MatColoringRegisterAllCalled = PETSC_FALSE;
5: const char *const MatColoringWeightTypes[] = {"RANDOM","LEXICAL","LF","SL","MatColoringWeightType","MAT_COLORING_WEIGHT_",NULL};
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: MatInitializePackage();
83: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
84: PetscObjectReference((PetscObject)m);
85: mc->mat = m;
86: mc->dist = 2; /* default to Jacobian computation case */
87: mc->maxcolors = IS_COLORING_MAX;
88: *mcptr = mc;
89: mc->valid = PETSC_FALSE;
90: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
91: mc->user_weights = NULL;
92: mc->user_lperm = NULL;
93: return(0);
94: }
96: /*@
97: MatColoringDestroy - Destroys the matrix coloring context
99: Collective on MatColoring
101: Input Parameter:
102: . mc - the MatColoring context
104: Level: beginner
106: .seealso: MatColoringCreate(), MatColoringApply()
107: @*/
108: PetscErrorCode MatColoringDestroy(MatColoring *mc)
109: {
113: if (--((PetscObject)(*mc))->refct > 0) {*mc = NULL; return(0);}
114: MatDestroy(&(*mc)->mat);
115: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
116: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
117: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
118: PetscHeaderDestroy(mc);
119: return(0);
120: }
122: /*@C
123: MatColoringSetType - Sets the type of coloring algorithm used
125: Collective on MatColoring
127: Input Parameters:
128: + mc - the MatColoring context
129: - type - the type of coloring
131: Level: beginner
133: Notes:
134: Possible types include the sequential types MATCOLORINGLF,
135: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
136: as a parallel MATCOLORINGMIS algorithm.
138: .seealso: MatColoringCreate(), MatColoringApply()
139: @*/
140: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
141: {
142: PetscBool match;
143: PetscErrorCode ierr,(*r)(MatColoring);
148: PetscObjectTypeCompare((PetscObject)mc,type,&match);
149: if (match) return(0);
150: PetscFunctionListFind(MatColoringList,type,&r);
151: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
152: if (mc->ops->destroy) {
153: (*(mc)->ops->destroy)(mc);
154: mc->ops->destroy = NULL;
155: }
156: mc->ops->apply = NULL;
157: mc->ops->view = NULL;
158: mc->ops->setfromoptions = NULL;
159: mc->ops->destroy = NULL;
161: PetscObjectChangeTypeName((PetscObject)mc,type);
162: (*r)(mc);
163: return(0);
164: }
166: /*@
167: MatColoringSetFromOptions - Sets MatColoring options from user parameters
169: Collective on MatColoring
171: Input Parameter:
172: . mc - MatColoring context
174: Options Database Keys:
175: + -mat_coloring_type - the type of coloring algorithm used
176: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
177: . -mat_coloring_distance - compute a distance 1,2,... coloring.
178: . -mat_coloring_view - print information about the coloring and the produced index sets
179: . -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
180: - -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)
182: Level: beginner
184: .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor()
185: @*/
186: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
187: {
188: PetscBool flg;
189: MatColoringType deft = MATCOLORINGSL;
190: char type[256];
192: PetscInt dist,maxcolors;
196: MatColoringGetDistance(mc,&dist);
197: if (dist == 2) deft = MATCOLORINGSL;
198: else deft = MATCOLORINGGREEDY;
199: MatColoringGetMaxColors(mc,&maxcolors);
200: MatColoringRegisterAll();
201: PetscObjectOptionsBegin((PetscObject)mc);
202: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
203: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
204: if (flg) {
205: MatColoringSetType(mc,type);
206: } else if (!((PetscObject)mc)->type_name) {
207: MatColoringSetType(mc,deft);
208: }
209: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
210: if (flg) {MatColoringSetDistance(mc,dist);}
211: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
212: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
213: if (mc->ops->setfromoptions) {
214: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
215: }
216: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
217: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
218: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
219: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
220: PetscOptionsEnd();
221: return(0);
222: }
224: /*@
225: MatColoringSetDistance - Sets the distance of the coloring
227: Logically Collective on MatColoring
229: Input Parameters:
230: + mc - the MatColoring context
231: - dist - the distance the coloring should compute
233: Level: beginner
235: Notes:
236: The distance of the coloring denotes the minimum number
237: of edges in the graph induced by the matrix any two vertices
238: of the same color are. Distance-1 colorings are the classical
239: coloring, where no two vertices of the same color are adjacent.
240: distance-2 colorings are useful for the computation of Jacobians.
242: .seealso: MatColoringGetDistance(), MatColoringApply()
243: @*/
244: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
245: {
248: mc->dist = dist;
249: return(0);
250: }
252: /*@
253: MatColoringGetDistance - Gets the distance of the coloring
255: Logically Collective on MatColoring
257: Input Parameter:
258: . mc - the MatColoring context
260: Output Parameter:
261: . dist - the current distance being used for the coloring.
263: Level: beginner
265: .seealso: MatColoringSetDistance(), MatColoringApply()
266: @*/
267: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
268: {
271: if (dist) *dist = mc->dist;
272: return(0);
273: }
275: /*@
276: MatColoringSetMaxColors - Sets the maximum number of colors
278: Logically Collective on MatColoring
280: Input Parameters:
281: + mc - the MatColoring context
282: - maxcolors - the maximum number of colors to produce
284: Level: beginner
286: Notes:
287: This may be used to compute a certain number of
288: independent sets from the graph. For instance, while using
289: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
290: not in a color are set to have color maxcolors+1, which is not
291: a valid color as they may be adjacent.
293: .seealso: MatColoringGetMaxColors(), MatColoringApply()
294: @*/
295: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
296: {
299: mc->maxcolors = maxcolors;
300: return(0);
301: }
303: /*@
304: MatColoringGetMaxColors - Gets the maximum number of colors
306: Logically Collective on MatColoring
308: Input Parameter:
309: . mc - the MatColoring context
311: Output Parameter:
312: . maxcolors - the current maximum number of colors to produce
314: Level: beginner
316: .seealso: MatColoringSetMaxColors(), MatColoringApply()
317: @*/
318: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
319: {
322: if (maxcolors) *maxcolors = mc->maxcolors;
323: return(0);
324: }
326: /*@
327: MatColoringApply - Apply the coloring to the matrix, producing index
328: sets corresponding to a number of independent sets in the induced
329: graph.
331: Collective on MatColoring
333: Input Parameters:
334: . mc - the MatColoring context
336: Output Parameter:
337: . coloring - the ISColoring instance containing the coloring
339: Level: beginner
341: .seealso: MatColoring, MatColoringCreate()
342: @*/
343: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
344: {
345: PetscErrorCode ierr;
346: PetscBool flg;
347: PetscViewerFormat format;
348: PetscViewer viewer;
349: PetscInt nc,ncolors;
353: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
354: (*mc->ops->apply)(mc,coloring);
355: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
357: /* valid */
358: if (mc->valid) {
359: MatColoringTest(mc,*coloring);
360: }
361: if (mc->valid_iscoloring) {
362: MatISColoringTest(mc->mat,*coloring);
363: }
365: /* view */
366: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
367: if (flg && !PetscPreLoadingOn) {
368: PetscViewerPushFormat(viewer,format);
369: MatColoringView(mc,viewer);
370: MatGetSize(mc->mat,NULL,&nc);
371: ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);
372: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
373: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
374: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
375: PetscViewerPopFormat(viewer);
376: PetscViewerDestroy(&viewer);
377: }
378: return(0);
379: }
381: /*@
382: MatColoringView - Output details about the MatColoring.
384: Collective on MatColoring
386: Input Parameters:
387: - mc - the MatColoring context
388: + viewer - the Viewer context
390: Level: beginner
392: .seealso: MatColoring, MatColoringApply()
393: @*/
394: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
395: {
397: PetscBool iascii;
401: if (!viewer) {
402: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
403: }
407: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
408: if (iascii) {
409: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
410: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
411: if (mc->maxcolors > 0) {
412: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
413: } else {
414: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
415: }
416: }
417: return(0);
418: }
420: /*@
421: MatColoringSetWeightType - Set the type of weight computation used.
423: Logically collective on MatColoring
425: Input Parameters:
426: - mc - the MatColoring context
427: + wt - the weight type
429: Level: beginner
431: .seealso: MatColoring, MatColoringWeightType
432: @*/
433: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
434: {
436: mc->weight_type = wt;
437: return(0);
439: }