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: {
32: MatInitializePackage();
33: PetscFunctionListAdd(&MatColoringList,sname,function);
34: return 0;
35: }
37: /*@
38: MatColoringCreate - Creates a matrix coloring context.
40: Collective on MatColoring
42: Input Parameters:
43: . comm - MPI communicator
45: Output Parameter:
46: . mcptr - the new MatColoring context
48: Options Database Keys:
49: + -mat_coloring_type - the type of coloring algorithm used. See MatColoringType.
50: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
51: . -mat_coloring_distance - compute a distance 1,2,... coloring.
52: . -mat_coloring_view - print information about the coloring and the produced index sets
53: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
54: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
56: Level: beginner
58: Notes:
59: A distance one coloring is useful, for example, multi-color SOR. A distance two coloring is for the finite difference computation of Jacobians
60: (see MatFDColoringCreate()).
62: Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the MatColoring object or from the mesh from which the
63: matrix comes from with DMCreateColoring(). In general using the mesh produces a more optimal coloring (fewer colors).
65: Some coloring types only support distance two colorings
67: .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate(), DMCreateColoring(), MatColoringType
68: @*/
69: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
70: {
71: MatColoring mc;
75: *mcptr = NULL;
77: MatInitializePackage();
78: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
79: PetscObjectReference((PetscObject)m);
80: mc->mat = m;
81: mc->dist = 2; /* default to Jacobian computation case */
82: mc->maxcolors = IS_COLORING_MAX;
83: *mcptr = mc;
84: mc->valid = PETSC_FALSE;
85: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
86: mc->user_weights = NULL;
87: mc->user_lperm = NULL;
88: return 0;
89: }
91: /*@
92: MatColoringDestroy - Destroys the matrix coloring context
94: Collective on MatColoring
96: Input Parameter:
97: . mc - the MatColoring context
99: Level: beginner
101: .seealso: MatColoringCreate(), MatColoringApply()
102: @*/
103: PetscErrorCode MatColoringDestroy(MatColoring *mc)
104: {
105: if (--((PetscObject)(*mc))->refct > 0) {*mc = NULL; return 0;}
106: MatDestroy(&(*mc)->mat);
107: if ((*mc)->ops->destroy) (*((*mc)->ops->destroy))(*mc);
108: if ((*mc)->user_weights) PetscFree((*mc)->user_weights);
109: if ((*mc)->user_lperm) PetscFree((*mc)->user_lperm);
110: PetscHeaderDestroy(mc);
111: return 0;
112: }
114: /*@C
115: MatColoringSetType - Sets the type of coloring algorithm used
117: Collective on MatColoring
119: Input Parameters:
120: + mc - the MatColoring context
121: - type - the type of coloring
123: Level: beginner
125: Notes:
126: Possible types include the sequential types MATCOLORINGLF,
127: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
128: as a parallel MATCOLORINGMIS algorithm.
130: .seealso: MatColoringCreate(), MatColoringApply()
131: @*/
132: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
133: {
134: PetscBool match;
135: PetscErrorCode (*r)(MatColoring);
139: PetscObjectTypeCompare((PetscObject)mc,type,&match);
140: if (match) return 0;
141: PetscFunctionListFind(MatColoringList,type,&r);
143: if (mc->ops->destroy) {
144: (*(mc)->ops->destroy)(mc);
145: mc->ops->destroy = NULL;
146: }
147: mc->ops->apply = NULL;
148: mc->ops->view = NULL;
149: mc->ops->setfromoptions = NULL;
150: mc->ops->destroy = NULL;
152: PetscObjectChangeTypeName((PetscObject)mc,type);
153: (*r)(mc);
154: return 0;
155: }
157: /*@
158: MatColoringSetFromOptions - Sets MatColoring options from user parameters
160: Collective on MatColoring
162: Input Parameter:
163: . mc - MatColoring context
165: Options Database Keys:
166: + -mat_coloring_type - the type of coloring algorithm used. See MatColoringType.
167: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
168: . -mat_coloring_distance - compute a distance 1,2,... coloring.
169: . -mat_coloring_view - print information about the coloring and the produced index sets
170: . -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
171: - -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)
173: Level: beginner
175: .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor(), MatColoringType
176: @*/
177: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
178: {
179: PetscBool flg;
180: MatColoringType deft = MATCOLORINGSL;
181: char type[256];
183: PetscInt dist,maxcolors;
186: MatColoringGetDistance(mc,&dist);
187: if (dist == 2) deft = MATCOLORINGSL;
188: else deft = MATCOLORINGGREEDY;
189: MatColoringGetMaxColors(mc,&maxcolors);
190: MatColoringRegisterAll();
191: PetscObjectOptionsBegin((PetscObject)mc);
192: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
193: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
194: if (flg) {
195: MatColoringSetType(mc,type);
196: } else if (!((PetscObject)mc)->type_name) {
197: MatColoringSetType(mc,deft);
198: }
199: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
200: if (flg) MatColoringSetDistance(mc,dist);
201: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
202: if (flg) MatColoringSetMaxColors(mc,maxcolors);
203: if (mc->ops->setfromoptions) {
204: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
205: }
206: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
207: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
208: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
209: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
210: PetscOptionsEnd();
211: return 0;
212: }
214: /*@
215: MatColoringSetDistance - Sets the distance of the coloring
217: Logically Collective on MatColoring
219: Input Parameters:
220: + mc - the MatColoring context
221: - dist - the distance the coloring should compute
223: Level: beginner
225: Notes:
226: The distance of the coloring denotes the minimum number
227: of edges in the graph induced by the matrix any two vertices
228: of the same color are. Distance-1 colorings are the classical
229: coloring, where no two vertices of the same color are adjacent.
230: distance-2 colorings are useful for the computation of Jacobians.
232: .seealso: MatColoringGetDistance(), MatColoringApply()
233: @*/
234: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
235: {
237: mc->dist = dist;
238: return 0;
239: }
241: /*@
242: MatColoringGetDistance - Gets the distance of the coloring
244: Logically Collective on MatColoring
246: Input Parameter:
247: . mc - the MatColoring context
249: Output Parameter:
250: . dist - the current distance being used for the coloring.
252: Level: beginner
254: .seealso: MatColoringSetDistance(), MatColoringApply()
255: @*/
256: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
257: {
259: if (dist) *dist = mc->dist;
260: return 0;
261: }
263: /*@
264: MatColoringSetMaxColors - Sets the maximum number of colors
266: Logically Collective on MatColoring
268: Input Parameters:
269: + mc - the MatColoring context
270: - maxcolors - the maximum number of colors to produce
272: Level: beginner
274: Notes:
275: This may be used to compute a certain number of
276: independent sets from the graph. For instance, while using
277: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
278: not in a color are set to have color maxcolors+1, which is not
279: a valid color as they may be adjacent.
281: .seealso: MatColoringGetMaxColors(), MatColoringApply()
282: @*/
283: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
284: {
286: mc->maxcolors = maxcolors;
287: return 0;
288: }
290: /*@
291: MatColoringGetMaxColors - Gets the maximum number of colors
293: Logically Collective on MatColoring
295: Input Parameter:
296: . mc - the MatColoring context
298: Output Parameter:
299: . maxcolors - the current maximum number of colors to produce
301: Level: beginner
303: .seealso: MatColoringSetMaxColors(), MatColoringApply()
304: @*/
305: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
306: {
308: if (maxcolors) *maxcolors = mc->maxcolors;
309: return 0;
310: }
312: /*@
313: MatColoringApply - Apply the coloring to the matrix, producing index
314: sets corresponding to a number of independent sets in the induced
315: graph.
317: Collective on MatColoring
319: Input Parameters:
320: . mc - the MatColoring context
322: Output Parameter:
323: . coloring - the ISColoring instance containing the coloring
325: Level: beginner
327: .seealso: MatColoring, MatColoringCreate()
328: @*/
329: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
330: {
331: PetscBool flg;
332: PetscViewerFormat format;
333: PetscViewer viewer;
334: PetscInt nc,ncolors;
338: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
339: (*mc->ops->apply)(mc,coloring);
340: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
342: /* valid */
343: if (mc->valid) {
344: MatColoringTest(mc,*coloring);
345: }
346: if (mc->valid_iscoloring) {
347: MatISColoringTest(mc->mat,*coloring);
348: }
350: /* view */
351: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
352: if (flg && !PetscPreLoadingOn) {
353: PetscViewerPushFormat(viewer,format);
354: MatColoringView(mc,viewer);
355: MatGetSize(mc->mat,NULL,&nc);
356: ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);
357: PetscViewerASCIIPrintf(viewer," Number of colors %" PetscInt_FMT "\n",ncolors);
358: PetscViewerASCIIPrintf(viewer," Number of total columns %" PetscInt_FMT "\n",nc);
359: if (nc <= 1000) ISColoringView(*coloring,viewer);
360: PetscViewerPopFormat(viewer);
361: PetscViewerDestroy(&viewer);
362: }
363: return 0;
364: }
366: /*@
367: MatColoringView - Output details about the MatColoring.
369: Collective on MatColoring
371: Input Parameters:
372: - mc - the MatColoring context
373: + viewer - the Viewer context
375: Level: beginner
377: .seealso: MatColoring, MatColoringApply()
378: @*/
379: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
380: {
381: PetscBool iascii;
384: if (!viewer) {
385: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
386: }
390: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
391: if (iascii) {
392: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
393: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
394: if (mc->maxcolors > 0) {
395: PetscViewerASCIIPrintf(viewer," Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n",mc->dist,mc->maxcolors);
396: } else {
397: PetscViewerASCIIPrintf(viewer," Distance %" PetscInt_FMT "\n",mc->dist);
398: }
399: }
400: return 0;
401: }
403: /*@
404: MatColoringSetWeightType - Set the type of weight computation used.
406: Logically collective on MatColoring
408: Input Parameters:
409: - mc - the MatColoring context
410: + wt - the weight type
412: Level: beginner
414: .seealso: MatColoring, MatColoringWeightType
415: @*/
416: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
417: {
418: mc->weight_type = wt;
419: return 0;
421: }