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: /*@
8: MatColoringRegister - Adds a new sparse matrix coloring to the matrix package.
10: Not Collective, No Fortran Support
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 `MatColoringSetType(part, "my_color")` or at runtime via the option
24: `-mat_coloring_type my_color`
26: .seealso: `MatColoringType`, `MatColoringRegisterDestroy()`, `MatColoringRegisterAll()`
27: @*/
28: PetscErrorCode MatColoringRegister(const char sname[], PetscErrorCode (*function)(MatColoring))
29: {
30: PetscFunctionBegin;
31: PetscCall(MatInitializePackage());
32: PetscCall(PetscFunctionListAdd(&MatColoringList, sname, function));
33: PetscFunctionReturn(PETSC_SUCCESS);
34: }
36: /*@
37: MatColoringCreate - Creates a matrix coloring context.
39: Collective
41: Input Parameter:
42: . m - a `Mat` from which a coloring is derived
44: Output Parameter:
45: . mcptr - the new `MatColoring` context
47: Options Database Keys:
48: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
49: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
50: . -mat_coloring_distance - compute a distance 1,2,... coloring.
51: . -mat_coloring_view - print information about the coloring and the produced index sets
52: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
53: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
55: Level: beginner
57: Notes:
58: A distance one coloring is useful, for example, multi-color SOR.
60: A distance two coloring is for the finite difference computation of Jacobians (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: `MatColoringSetFromOptions()`, `MatColoring`, `MatColoringApply()`, `MatFDColoringCreate()`, `DMCreateColoring()`, `MatColoringType`
68: @*/
69: PetscErrorCode MatColoringCreate(Mat m, MatColoring *mcptr)
70: {
71: MatColoring mc;
73: PetscFunctionBegin;
75: PetscAssertPointer(mcptr, 2);
76: PetscCall(MatInitializePackage());
78: PetscCall(PetscHeaderCreate(mc, MAT_COLORING_CLASSID, "MatColoring", "Matrix coloring", "MatColoring", PetscObjectComm((PetscObject)m), MatColoringDestroy, MatColoringView));
79: PetscCall(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: PetscFunctionReturn(PETSC_SUCCESS);
89: }
91: /*@
92: MatColoringDestroy - Destroys the matrix coloring context
94: Collective
96: Input Parameter:
97: . mc - the `MatColoring` context
99: Level: beginner
101: .seealso: `MatColoring`, `MatColoringCreate()`, `MatColoringApply()`
102: @*/
103: PetscErrorCode MatColoringDestroy(MatColoring *mc)
104: {
105: PetscFunctionBegin;
106: if (--((PetscObject)*mc)->refct > 0) {
107: *mc = NULL;
108: PetscFunctionReturn(PETSC_SUCCESS);
109: }
110: PetscCall(MatDestroy(&(*mc)->mat));
111: PetscTryTypeMethod(*mc, destroy);
112: PetscCall(PetscFree2((*mc)->user_weights, (*mc)->user_lperm));
113: PetscCall(PetscHeaderDestroy(mc));
114: PetscFunctionReturn(PETSC_SUCCESS);
115: }
117: /*@
118: MatColoringSetType - Sets the type of coloring algorithm used
120: Collective
122: Input Parameters:
123: + mc - the `MatColoring` context
124: - type - the type of coloring
126: Options Database Key:
127: . -mat_coloring_type type - the name of the type
129: Level: beginner
131: Note:
132: Possible types include the sequential types `MATCOLORINGLF`,
133: `MATCOLORINGSL`, and `MATCOLORINGID` from the MINPACK package as well
134: as a parallel `MATCOLORINGGREEDY` algorithm.
136: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringType`, `MatColoringCreate()`, `MatColoringApply()`
137: @*/
138: PetscErrorCode MatColoringSetType(MatColoring mc, MatColoringType type)
139: {
140: PetscBool match;
141: PetscErrorCode (*r)(MatColoring);
143: PetscFunctionBegin;
145: PetscAssertPointer(type, 2);
146: PetscCall(PetscObjectTypeCompare((PetscObject)mc, type, &match));
147: if (match) PetscFunctionReturn(PETSC_SUCCESS);
148: PetscCall(PetscFunctionListFind(MatColoringList, type, &r));
149: PetscCheck(r, PetscObjectComm((PetscObject)mc), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unable to find requested MatColoring type %s", type);
151: PetscTryTypeMethod(mc, destroy);
152: mc->ops->destroy = NULL;
153: mc->ops->apply = NULL;
154: mc->ops->view = NULL;
155: mc->ops->setfromoptions = NULL;
156: mc->ops->destroy = NULL;
158: PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
159: PetscCall((*r)(mc));
160: PetscFunctionReturn(PETSC_SUCCESS);
161: }
163: /*@
164: MatColoringSetFromOptions - Sets `MatColoring` options from options database
166: Collective
168: Input Parameter:
169: . mc - `MatColoring` context
171: Options Database Keys:
172: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
173: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
174: . -mat_coloring_distance - compute a distance 1,2,... coloring.
175: . -mat_coloring_view - print information about the coloring and the produced index sets
176: . -snes_fd_color - instruct SNES to using coloring and then `MatFDColoring` to compute the Jacobians
177: - -snes_fd_color_use_mat - instruct `SNES` to color the matrix directly instead of the `DM` from which the matrix comes (the default)
179: Level: beginner
181: .seealso: `MatColoring`, `MatColoringApply()`, `MatColoringSetDistance()`, `MatColoringSetType()`, `SNESComputeJacobianDefaultColor()`, `MatColoringType`
182: @*/
183: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
184: {
185: PetscBool flg;
186: MatColoringType deft = MATCOLORINGGREEDY;
187: char type[256];
188: PetscInt dist, maxcolors;
190: PetscFunctionBegin;
192: PetscCall(MatColoringGetDistance(mc, &dist));
193: if (dist == 2) deft = MATCOLORINGSL;
194: PetscCall(MatColoringGetMaxColors(mc, &maxcolors));
195: PetscCall(MatColoringRegisterAll());
196: PetscObjectOptionsBegin((PetscObject)mc);
197: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
198: PetscCall(PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, sizeof(type), &flg));
199: if (flg) {
200: PetscCall(MatColoringSetType(mc, type));
201: } else if (!((PetscObject)mc)->type_name) {
202: PetscCall(MatColoringSetType(mc, deft));
203: }
204: PetscCall(PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg));
205: if (flg) PetscCall(MatColoringSetDistance(mc, dist));
206: PetscCall(PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg));
207: if (flg) PetscCall(MatColoringSetMaxColors(mc, maxcolors));
208: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
209: PetscCall(PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL));
210: PetscCall(PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL));
211: PetscCall(PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL));
212: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject));
213: PetscOptionsEnd();
214: PetscFunctionReturn(PETSC_SUCCESS);
215: }
217: /*@
218: MatColoringSetDistance - Sets the distance of the coloring
220: Logically Collective
222: Input Parameters:
223: + mc - the `MatColoring` context
224: - dist - the distance the coloring should compute
226: Options Database Key:
227: . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
229: Level: beginner
231: Note:
232: The distance of the coloring denotes the minimum number
233: of edges in the graph induced by the matrix any two vertices
234: of the same color are. Distance-1 colorings are the classical
235: coloring, where no two vertices of the same color are adjacent.
236: distance-2 colorings are useful for the computation of Jacobians.
238: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
239: @*/
240: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
241: {
242: PetscFunctionBegin;
244: mc->dist = dist;
245: PetscFunctionReturn(PETSC_SUCCESS);
246: }
248: /*@
249: MatColoringGetDistance - Gets the distance of the coloring
251: Logically Collective
253: Input Parameter:
254: . mc - the `MatColoring` context
256: Output Parameter:
257: . dist - the current distance being used for the coloring.
259: Level: beginner
261: Note:
262: The distance of the coloring denotes the minimum number
263: of edges in the graph induced by the matrix any two vertices
264: of the same color are. Distance-1 colorings are the classical
265: coloring, where no two vertices of the same color are adjacent.
266: distance-2 colorings are useful for the computation of Jacobians.
268: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
269: @*/
270: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
271: {
272: PetscFunctionBegin;
274: if (dist) *dist = mc->dist;
275: PetscFunctionReturn(PETSC_SUCCESS);
276: }
278: /*@
279: MatColoringSetMaxColors - Sets the maximum number of colors to produce
281: Logically Collective
283: Input Parameters:
284: + mc - the `MatColoring` context
285: - maxcolors - the maximum number of colors to produce
287: Level: beginner
289: Notes:
290: Vertices not in an available color are set to have color maxcolors+1, which is not
291: a valid color as they may be adjacent.
293: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
295: This may be used to compute a certain number of
296: independent sets from the graph. For instance, while using
297: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
299: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
300: @*/
301: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
302: {
303: PetscFunctionBegin;
305: mc->maxcolors = maxcolors;
306: PetscFunctionReturn(PETSC_SUCCESS);
307: }
309: /*@
310: MatColoringGetMaxColors - Gets the maximum number of colors
312: Logically Collective
314: Input Parameter:
315: . mc - the `MatColoring` context
317: Output Parameter:
318: . maxcolors - the current maximum number of colors to produce
320: Level: beginner
322: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
323: @*/
324: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
325: {
326: PetscFunctionBegin;
328: if (maxcolors) *maxcolors = mc->maxcolors;
329: PetscFunctionReturn(PETSC_SUCCESS);
330: }
332: /*@
333: MatColoringApply - Apply the coloring to the matrix, producing index
334: sets corresponding to a number of independent sets in the induced
335: graph.
337: Collective
339: Input Parameter:
340: . mc - the `MatColoring` context
342: Output Parameter:
343: . coloring - the `ISColoring` instance containing the coloring
345: Level: beginner
347: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
348: @*/
349: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
350: {
351: PetscBool flg;
352: PetscViewerFormat format;
353: PetscViewer viewer;
354: PetscInt nc, ncolors;
356: PetscFunctionBegin;
358: PetscAssertPointer(coloring, 2);
359: PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
360: PetscUseTypeMethod(mc, apply, coloring);
361: PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));
363: /* valid */
364: if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
365: if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
367: /* view */
368: PetscCall(PetscOptionsCreateViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg));
369: if (flg && !PetscPreLoadingOn) {
370: PetscCall(PetscViewerPushFormat(viewer, format));
371: PetscCall(MatColoringView(mc, viewer));
372: PetscCall(MatGetSize(mc->mat, NULL, &nc));
373: PetscCall(ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL));
374: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors));
375: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc));
376: if (nc <= 1000) PetscCall(ISColoringView(*coloring, viewer));
377: PetscCall(PetscViewerPopFormat(viewer));
378: PetscCall(PetscViewerDestroy(&viewer));
379: }
380: PetscFunctionReturn(PETSC_SUCCESS);
381: }
383: /*@
384: MatColoringView - Output details about the `MatColoring`.
386: Collective
388: Input Parameters:
389: + mc - the `MatColoring` context
390: - viewer - the Viewer context
392: Level: beginner
394: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
395: @*/
396: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
397: {
398: PetscBool isascii;
400: PetscFunctionBegin;
402: if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
404: PetscCheckSameComm(mc, 1, viewer, 2);
406: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
407: if (isascii) {
408: PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
409: PetscCall(PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
410: if (mc->maxcolors > 0) {
411: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
412: } else {
413: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist));
414: }
415: }
416: PetscFunctionReturn(PETSC_SUCCESS);
417: }
419: /*@
420: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
422: Logically Collective
424: Input Parameters:
425: + mc - the `MatColoring` context
426: - wt - the weight type
428: Level: beginner
430: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
431: @*/
432: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
433: {
434: PetscFunctionBegin;
435: mc->weight_type = wt;
436: PetscFunctionReturn(PETSC_SUCCESS);
437: }