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: }
97: /*@
98: MatColoringDestroy - Destroys the matrix coloring context
100: Collective on MatColoring
102: Input Parameter:
103: . mc - the MatColoring context
105: Level: beginner
107: .seealso: MatColoringCreate(), MatColoringApply()
108: @*/
109: PetscErrorCode MatColoringDestroy(MatColoring *mc)
110: {
114: if (--((PetscObject)(*mc))->refct > 0) {*mc = NULL; return(0);}
115: MatDestroy(&(*mc)->mat);
116: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
117: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
118: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
119: PetscHeaderDestroy(mc);
120: return(0);
121: }
123: /*@C
124: MatColoringSetType - Sets the type of coloring algorithm used
126: Collective on MatColoring
128: Input Parameter:
129: + mc - the MatColoring context
130: - type - the type of coloring
132: Level: beginner
134: Notes:
135: Possible types include the sequential types MATCOLORINGLF,
136: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
137: as a parallel MATCOLORINGMIS algorithm.
139: .seealso: MatColoringCreate(), MatColoringApply()
140: @*/
141: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
142: {
143: PetscBool match;
144: PetscErrorCode ierr,(*r)(MatColoring);
149: PetscObjectTypeCompare((PetscObject)mc,type,&match);
150: if (match) return(0);
151: PetscFunctionListFind(MatColoringList,type,&r);
152: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
153: if (mc->ops->destroy) {
154: (*(mc)->ops->destroy)(mc);
155: mc->ops->destroy = NULL;
156: }
157: mc->ops->apply = NULL;
158: mc->ops->view = NULL;
159: mc->ops->setfromoptions = NULL;
160: mc->ops->destroy = NULL;
162: PetscObjectChangeTypeName((PetscObject)mc,type);
163: (*r)(mc);
164: return(0);
165: }
167: /*@
168: MatColoringSetFromOptions - Sets MatColoring options from user parameters
170: Collective on MatColoring
172: Input Parameters:
173: . mc - MatColoring context
175: Options Database Keys:
176: + -mat_coloring_type - the type of coloring algorithm used
177: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
178: . -mat_coloring_distance - compute a distance 1,2,... coloring.
179: . -mat_coloring_view - print information about the coloring and the produced index sets
180: . -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
181: - -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)
183: Level: beginner
185: .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor()
186: @*/
187: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
188: {
189: PetscBool flg;
190: MatColoringType deft = MATCOLORINGSL;
191: char type[256];
193: PetscInt dist,maxcolors;
197: MatColoringGetDistance(mc,&dist);
198: if (dist == 2) deft = MATCOLORINGSL;
199: else deft = MATCOLORINGGREEDY;
200: MatColoringGetMaxColors(mc,&maxcolors);
201: MatColoringRegisterAll();
202: PetscObjectOptionsBegin((PetscObject)mc);
203: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
204: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
205: if (flg) {
206: MatColoringSetType(mc,type);
207: } else if (!((PetscObject)mc)->type_name) {
208: MatColoringSetType(mc,deft);
209: }
210: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
211: if (flg) {MatColoringSetDistance(mc,dist);}
212: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
213: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
214: if (mc->ops->setfromoptions) {
215: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
216: }
217: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
218: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
219: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
220: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
221: PetscOptionsEnd();
222: return(0);
223: }
225: /*@
226: MatColoringSetDistance - Sets the distance of the coloring
228: Logically Collective on MatColoring
230: Input Parameters:
231: + mc - the MatColoring context
232: - dist - the distance the coloring should compute
234: Level: beginner
236: Notes:
237: The distance of the coloring denotes the minimum number
238: of edges in the graph induced by the matrix any two vertices
239: of the same color are. Distance-1 colorings are the classical
240: coloring, where no two vertices of the same color are adjacent.
241: distance-2 colorings are useful for the computation of Jacobians.
243: .seealso: MatColoringGetDistance(), MatColoringApply()
244: @*/
245: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
246: {
249: mc->dist = dist;
250: return(0);
251: }
253: /*@
254: MatColoringGetDistance - Gets the distance of the coloring
256: Logically Collective on MatColoring
258: Input Parameter:
259: . mc - the MatColoring context
261: Output Parameter:
262: . dist - the current distance being used for the coloring.
264: Level: beginner
266: .seealso: MatColoringSetDistance(), MatColoringApply()
267: @*/
268: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
269: {
272: if (dist) *dist = mc->dist;
273: return(0);
274: }
276: /*@
277: MatColoringSetMaxColors - Sets the maximum number of colors
279: Logically Collective on MatColoring
281: Input Parameter:
282: + mc - the MatColoring context
283: - maxcolors - the maximum number of colors to produce
285: Level: beginner
287: Notes:
288: This may be used to compute a certain number of
289: independent sets from the graph. For instance, while using
290: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
291: not in a color are set to have color maxcolors+1, which is not
292: a valid color as they may be adjacent.
294: .seealso: MatColoringGetMaxColors(), MatColoringApply()
295: @*/
296: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
297: {
300: mc->maxcolors = maxcolors;
301: return(0);
302: }
304: /*@
305: MatColoringGetMaxColors - Gets the maximum number of colors
307: Logically Collective on MatColoring
309: Input Parameter:
310: . mc - the MatColoring context
312: Output Parameter:
313: . maxcolors - the current maximum number of colors to produce
315: Level: beginner
317: .seealso: MatColoringSetMaxColors(), MatColoringApply()
318: @*/
319: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
320: {
323: if (maxcolors) *maxcolors = mc->maxcolors;
324: return(0);
325: }
327: /*@
328: MatColoringApply - Apply the coloring to the matrix, producing index
329: sets corresponding to a number of independent sets in the induced
330: graph.
332: Collective on MatColoring
334: Input Parameters:
335: . mc - the MatColoring context
337: Output Parameter:
338: . coloring - the ISColoring instance containing the coloring
340: Level: beginner
342: .seealso: MatColoring, MatColoringCreate()
343: @*/
344: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
345: {
346: PetscErrorCode ierr;
347: PetscBool flg;
348: PetscViewerFormat format;
349: PetscViewer viewer;
350: PetscInt nc,ncolors;
354: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
355: (*mc->ops->apply)(mc,coloring);
356: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
358: /* valid */
359: if (mc->valid) {
360: MatColoringTest(mc,*coloring);
361: }
362: if (mc->valid_iscoloring) {
363: MatISColoringTest(mc->mat,*coloring);
364: }
366: /* view */
367: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
368: if (flg && !PetscPreLoadingOn) {
369: PetscViewerPushFormat(viewer,format);
370: MatColoringView(mc,viewer);
371: MatGetSize(mc->mat,NULL,&nc);
372: ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);
373: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
374: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
375: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
376: PetscViewerPopFormat(viewer);
377: PetscViewerDestroy(&viewer);
378: }
379: return(0);
380: }
382: /*@
383: MatColoringView - Output details about the MatColoring.
385: Collective on MatColoring
387: Input Parameters:
388: - mc - the MatColoring context
389: + viewer - the Viewer context
391: Level: beginner
393: .seealso: MatColoring, MatColoringApply()
394: @*/
395: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
396: {
398: PetscBool iascii;
402: if (!viewer) {
403: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
404: }
408: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
409: if (iascii) {
410: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
411: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
412: if (mc->maxcolors > 0) {
413: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
414: } else {
415: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
416: }
417: }
418: return(0);
419: }
421: /*@
422: MatColoringSetWeightType - Set the type of weight computation used.
424: Logically collective on MatColoring
426: Input Parameters:
427: - mc - the MatColoring context
428: + wt - the weight type
430: Level: beginner
432: .seealso: MatColoring, MatColoringWeightType
433: @*/
434: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
435: {
437: mc->weight_type = wt;
438: return(0);
440: }