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: Example 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: `MatColoringType`, `MatColoringRegisterDestroy()`, `MatColoringRegisterAll()`
29: @*/
30: PetscErrorCode MatColoringRegister(const char sname[], PetscErrorCode (*function)(MatColoring))
31: {
32: PetscFunctionBegin;
33: PetscCall(MatInitializePackage());
34: PetscCall(PetscFunctionListAdd(&MatColoringList, sname, function));
35: PetscFunctionReturn(PETSC_SUCCESS);
36: }
38: /*@
39: MatColoringCreate - Creates a matrix coloring context.
41: Collective
43: Input Parameter:
44: . m - MPI communicator
46: Output Parameter:
47: . mcptr - the new `MatColoring` context
49: Options Database Keys:
50: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
51: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
52: . -mat_coloring_distance - compute a distance 1,2,... coloring.
53: . -mat_coloring_view - print information about the coloring and the produced index sets
54: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
55: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
57: Level: beginner
59: Notes:
60: A distance one coloring is useful, for example, multi-color SOR.
62: A distance two coloring is for the finite difference computation of Jacobians (see `MatFDColoringCreate()`).
64: Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the `MatColoring` object or from the mesh from which the
65: matrix comes from with `DMCreateColoring()`. In general using the mesh produces a more optimal coloring (fewer colors).
67: Some coloring types only support distance two colorings
69: .seealso: `MatColoringSetFromOptions()`, `MatColoring`, `MatColoringApply()`, `MatFDColoringCreate()`, `DMCreateColoring()`, `MatColoringType`
70: @*/
71: PetscErrorCode MatColoringCreate(Mat m, MatColoring *mcptr)
72: {
73: MatColoring mc;
75: PetscFunctionBegin;
77: PetscAssertPointer(mcptr, 2);
78: *mcptr = NULL;
80: PetscCall(MatInitializePackage());
81: PetscCall(PetscHeaderCreate(mc, MAT_COLORING_CLASSID, "MatColoring", "Matrix coloring", "MatColoring", PetscObjectComm((PetscObject)m), MatColoringDestroy, MatColoringView));
82: PetscCall(PetscObjectReference((PetscObject)m));
83: mc->mat = m;
84: mc->dist = 2; /* default to Jacobian computation case */
85: mc->maxcolors = IS_COLORING_MAX;
86: *mcptr = mc;
87: mc->valid = PETSC_FALSE;
88: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
89: mc->user_weights = NULL;
90: mc->user_lperm = NULL;
91: PetscFunctionReturn(PETSC_SUCCESS);
92: }
94: /*@
95: MatColoringDestroy - Destroys the matrix coloring context
97: Collective
99: Input Parameter:
100: . mc - the `MatColoring` context
102: Level: beginner
104: .seealso: `MatColoring`, `MatColoringCreate()`, `MatColoringApply()`
105: @*/
106: PetscErrorCode MatColoringDestroy(MatColoring *mc)
107: {
108: PetscFunctionBegin;
109: if (--((PetscObject)(*mc))->refct > 0) {
110: *mc = NULL;
111: PetscFunctionReturn(PETSC_SUCCESS);
112: }
113: PetscCall(MatDestroy(&(*mc)->mat));
114: if ((*mc)->ops->destroy) PetscCall((*((*mc)->ops->destroy))(*mc));
115: if ((*mc)->user_weights) PetscCall(PetscFree((*mc)->user_weights));
116: if ((*mc)->user_lperm) PetscCall(PetscFree((*mc)->user_lperm));
117: PetscCall(PetscHeaderDestroy(mc));
118: PetscFunctionReturn(PETSC_SUCCESS);
119: }
121: /*@C
122: MatColoringSetType - Sets the type of coloring algorithm used
124: Collective
126: Input Parameters:
127: + mc - the `MatColoring` context
128: - type - the type of coloring
130: Options Database Key:
131: . -mat_coloring_type type - the name of the type
133: Level: beginner
135: Note:
136: Possible types include the sequential types `MATCOLORINGLF`,
137: `MATCOLORINGSL`, and `MATCOLORINGID` from the MINPACK package as well
138: as a parallel `MATCOLORINGGREEDY` algorithm.
140: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringType`, `MatColoringCreate()`, `MatColoringApply()`
141: @*/
142: PetscErrorCode MatColoringSetType(MatColoring mc, MatColoringType type)
143: {
144: PetscBool match;
145: PetscErrorCode (*r)(MatColoring);
147: PetscFunctionBegin;
149: PetscAssertPointer(type, 2);
150: PetscCall(PetscObjectTypeCompare((PetscObject)mc, type, &match));
151: if (match) PetscFunctionReturn(PETSC_SUCCESS);
152: PetscCall(PetscFunctionListFind(MatColoringList, type, &r));
153: PetscCheck(r, PetscObjectComm((PetscObject)mc), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unable to find requested MatColoring type %s", type);
154: if (mc->ops->destroy) {
155: PetscCall((*(mc)->ops->destroy)(mc));
156: mc->ops->destroy = NULL;
157: }
158: mc->ops->apply = NULL;
159: mc->ops->view = NULL;
160: mc->ops->setfromoptions = NULL;
161: mc->ops->destroy = NULL;
163: PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
164: PetscCall((*r)(mc));
165: PetscFunctionReturn(PETSC_SUCCESS);
166: }
168: /*@
169: MatColoringSetFromOptions - Sets `MatColoring` options from options database
171: Collective
173: Input Parameter:
174: . mc - `MatColoring` context
176: Options Database Keys:
177: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
178: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
179: . -mat_coloring_distance - compute a distance 1,2,... coloring.
180: . -mat_coloring_view - print information about the coloring and the produced index sets
181: . -snes_fd_color - instruct SNES to using coloring and then `MatFDColoring` to compute the Jacobians
182: - -snes_fd_color_use_mat - instruct `SNES` to color the matrix directly instead of the `DM` from which the matrix comes (the default)
184: Level: beginner
186: .seealso: `MatColoring`, `MatColoringApply()`, `MatColoringSetDistance()`, `MatColoringSetType()`, `SNESComputeJacobianDefaultColor()`, `MatColoringType`
187: @*/
188: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
189: {
190: PetscBool flg;
191: MatColoringType deft = MATCOLORINGSL;
192: char type[256];
193: PetscInt dist, maxcolors;
195: PetscFunctionBegin;
197: PetscCall(MatColoringGetDistance(mc, &dist));
198: if (dist == 2) deft = MATCOLORINGSL;
199: else deft = MATCOLORINGGREEDY;
200: PetscCall(MatColoringGetMaxColors(mc, &maxcolors));
201: PetscCall(MatColoringRegisterAll());
202: PetscObjectOptionsBegin((PetscObject)mc);
203: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
204: PetscCall(PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, 256, &flg));
205: if (flg) {
206: PetscCall(MatColoringSetType(mc, type));
207: } else if (!((PetscObject)mc)->type_name) {
208: PetscCall(MatColoringSetType(mc, deft));
209: }
210: PetscCall(PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg));
211: if (flg) PetscCall(MatColoringSetDistance(mc, dist));
212: PetscCall(PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg));
213: if (flg) PetscCall(MatColoringSetMaxColors(mc, maxcolors));
214: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
215: PetscCall(PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL));
216: PetscCall(PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL));
217: PetscCall(PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL));
218: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject));
219: PetscOptionsEnd();
220: PetscFunctionReturn(PETSC_SUCCESS);
221: }
223: /*@
224: MatColoringSetDistance - Sets the distance of the coloring
226: Logically Collective
228: Input Parameters:
229: + mc - the `MatColoring` context
230: - dist - the distance the coloring should compute
232: Options Database Key:
233: . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
235: Level: beginner
237: Note:
238: The distance of the coloring denotes the minimum number
239: of edges in the graph induced by the matrix any two vertices
240: of the same color are. Distance-1 colorings are the classical
241: coloring, where no two vertices of the same color are adjacent.
242: distance-2 colorings are useful for the computation of Jacobians.
244: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
245: @*/
246: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
247: {
248: PetscFunctionBegin;
250: mc->dist = dist;
251: PetscFunctionReturn(PETSC_SUCCESS);
252: }
254: /*@
255: MatColoringGetDistance - Gets the distance of the coloring
257: Logically Collective
259: Input Parameter:
260: . mc - the `MatColoring` context
262: Output Parameter:
263: . dist - the current distance being used for the coloring.
265: Level: beginner
267: Note:
268: The distance of the coloring denotes the minimum number
269: of edges in the graph induced by the matrix any two vertices
270: of the same color are. Distance-1 colorings are the classical
271: coloring, where no two vertices of the same color are adjacent.
272: distance-2 colorings are useful for the computation of Jacobians.
274: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
275: @*/
276: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
277: {
278: PetscFunctionBegin;
280: if (dist) *dist = mc->dist;
281: PetscFunctionReturn(PETSC_SUCCESS);
282: }
284: /*@
285: MatColoringSetMaxColors - Sets the maximum number of colors to produce
287: Logically Collective
289: Input Parameters:
290: + mc - the `MatColoring` context
291: - maxcolors - the maximum number of colors to produce
293: Level: beginner
295: Notes:
296: Vertices not in an available color are set to have color maxcolors+1, which is not
297: a valid color as they may be adjacent.
299: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
301: This may be used to compute a certain number of
302: independent sets from the graph. For instance, while using
303: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
305: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
306: @*/
307: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
308: {
309: PetscFunctionBegin;
311: mc->maxcolors = maxcolors;
312: PetscFunctionReturn(PETSC_SUCCESS);
313: }
315: /*@
316: MatColoringGetMaxColors - Gets the maximum number of colors
318: Logically Collective
320: Input Parameter:
321: . mc - the `MatColoring` context
323: Output Parameter:
324: . maxcolors - the current maximum number of colors to produce
326: Level: beginner
328: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
329: @*/
330: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
331: {
332: PetscFunctionBegin;
334: if (maxcolors) *maxcolors = mc->maxcolors;
335: PetscFunctionReturn(PETSC_SUCCESS);
336: }
338: /*@
339: MatColoringApply - Apply the coloring to the matrix, producing index
340: sets corresponding to a number of independent sets in the induced
341: graph.
343: Collective
345: Input Parameter:
346: . mc - the `MatColoring` context
348: Output Parameter:
349: . coloring - the `ISColoring` instance containing the coloring
351: Level: beginner
353: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
354: @*/
355: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
356: {
357: PetscBool flg;
358: PetscViewerFormat format;
359: PetscViewer viewer;
360: PetscInt nc, ncolors;
362: PetscFunctionBegin;
364: PetscAssertPointer(coloring, 2);
365: PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
366: PetscUseTypeMethod(mc, apply, coloring);
367: PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));
369: /* valid */
370: if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
371: if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
373: /* view */
374: PetscCall(PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg));
375: if (flg && !PetscPreLoadingOn) {
376: PetscCall(PetscViewerPushFormat(viewer, format));
377: PetscCall(MatColoringView(mc, viewer));
378: PetscCall(MatGetSize(mc->mat, NULL, &nc));
379: PetscCall(ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL));
380: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors));
381: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc));
382: if (nc <= 1000) PetscCall(ISColoringView(*coloring, viewer));
383: PetscCall(PetscViewerPopFormat(viewer));
384: PetscCall(PetscViewerDestroy(&viewer));
385: }
386: PetscFunctionReturn(PETSC_SUCCESS);
387: }
389: /*@
390: MatColoringView - Output details about the `MatColoring`.
392: Collective
394: Input Parameters:
395: + mc - the `MatColoring` context
396: - viewer - the Viewer context
398: Level: beginner
400: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
401: @*/
402: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
403: {
404: PetscBool iascii;
406: PetscFunctionBegin;
408: if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
410: PetscCheckSameComm(mc, 1, viewer, 2);
412: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii));
413: if (iascii) {
414: PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
415: PetscCall(PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
416: if (mc->maxcolors > 0) {
417: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
418: } else {
419: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist));
420: }
421: }
422: PetscFunctionReturn(PETSC_SUCCESS);
423: }
425: /*@
426: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
428: Logically Collective
430: Input Parameters:
431: + mc - the `MatColoring` context
432: - wt - the weight type
434: Level: beginner
436: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
437: @*/
438: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
439: {
440: PetscFunctionBegin;
441: mc->weight_type = wt;
442: PetscFunctionReturn(PETSC_SUCCESS);
443: }