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, 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 - MPI communicator
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: *mcptr = NULL;
78: PetscCall(MatInitializePackage());
79: PetscCall(PetscHeaderCreate(mc, MAT_COLORING_CLASSID, "MatColoring", "Matrix coloring", "MatColoring", PetscObjectComm((PetscObject)m), MatColoringDestroy, MatColoringView));
80: PetscCall(PetscObjectReference((PetscObject)m));
81: mc->mat = m;
82: mc->dist = 2; /* default to Jacobian computation case */
83: mc->maxcolors = IS_COLORING_MAX;
84: *mcptr = mc;
85: mc->valid = PETSC_FALSE;
86: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
87: mc->user_weights = NULL;
88: mc->user_lperm = NULL;
89: PetscFunctionReturn(PETSC_SUCCESS);
90: }
92: /*@
93: MatColoringDestroy - Destroys the matrix coloring context
95: Collective
97: Input Parameter:
98: . mc - the `MatColoring` context
100: Level: beginner
102: .seealso: `MatColoring`, `MatColoringCreate()`, `MatColoringApply()`
103: @*/
104: PetscErrorCode MatColoringDestroy(MatColoring *mc)
105: {
106: PetscFunctionBegin;
107: if (--((PetscObject)*mc)->refct > 0) {
108: *mc = NULL;
109: PetscFunctionReturn(PETSC_SUCCESS);
110: }
111: PetscCall(MatDestroy(&(*mc)->mat));
112: PetscTryTypeMethod(*mc, destroy);
113: PetscCall(PetscFree((*mc)->user_weights));
114: PetscCall(PetscFree((*mc)->user_lperm));
115: PetscCall(PetscHeaderDestroy(mc));
116: PetscFunctionReturn(PETSC_SUCCESS);
117: }
119: /*@
120: MatColoringSetType - Sets the type of coloring algorithm used
122: Collective
124: Input Parameters:
125: + mc - the `MatColoring` context
126: - type - the type of coloring
128: Options Database Key:
129: . -mat_coloring_type type - the name of the type
131: Level: beginner
133: Note:
134: Possible types include the sequential types `MATCOLORINGLF`,
135: `MATCOLORINGSL`, and `MATCOLORINGID` from the MINPACK package as well
136: as a parallel `MATCOLORINGGREEDY` algorithm.
138: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringType`, `MatColoringCreate()`, `MatColoringApply()`
139: @*/
140: PetscErrorCode MatColoringSetType(MatColoring mc, MatColoringType type)
141: {
142: PetscBool match;
143: PetscErrorCode (*r)(MatColoring);
145: PetscFunctionBegin;
147: PetscAssertPointer(type, 2);
148: PetscCall(PetscObjectTypeCompare((PetscObject)mc, type, &match));
149: if (match) PetscFunctionReturn(PETSC_SUCCESS);
150: PetscCall(PetscFunctionListFind(MatColoringList, type, &r));
151: PetscCheck(r, PetscObjectComm((PetscObject)mc), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unable to find requested MatColoring type %s", type);
153: PetscTryTypeMethod(mc, destroy);
154: mc->ops->destroy = NULL;
155: mc->ops->apply = NULL;
156: mc->ops->view = NULL;
157: mc->ops->setfromoptions = NULL;
158: mc->ops->destroy = NULL;
160: PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
161: PetscCall((*r)(mc));
162: PetscFunctionReturn(PETSC_SUCCESS);
163: }
165: /*@
166: MatColoringSetFromOptions - Sets `MatColoring` options from options database
168: Collective
170: Input Parameter:
171: . mc - `MatColoring` context
173: Options Database Keys:
174: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
175: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
176: . -mat_coloring_distance - compute a distance 1,2,... coloring.
177: . -mat_coloring_view - print information about the coloring and the produced index sets
178: . -snes_fd_color - instruct SNES to using coloring and then `MatFDColoring` to compute the Jacobians
179: - -snes_fd_color_use_mat - instruct `SNES` to color the matrix directly instead of the `DM` from which the matrix comes (the default)
181: Level: beginner
183: .seealso: `MatColoring`, `MatColoringApply()`, `MatColoringSetDistance()`, `MatColoringSetType()`, `SNESComputeJacobianDefaultColor()`, `MatColoringType`
184: @*/
185: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
186: {
187: PetscBool flg;
188: MatColoringType deft = MATCOLORINGSL;
189: char type[256];
190: PetscInt dist, maxcolors;
192: PetscFunctionBegin;
194: PetscCall(MatColoringGetDistance(mc, &dist));
195: if (dist == 2) deft = MATCOLORINGSL;
196: else deft = MATCOLORINGGREEDY;
197: PetscCall(MatColoringGetMaxColors(mc, &maxcolors));
198: PetscCall(MatColoringRegisterAll());
199: PetscObjectOptionsBegin((PetscObject)mc);
200: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
201: PetscCall(PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, 256, &flg));
202: if (flg) {
203: PetscCall(MatColoringSetType(mc, type));
204: } else if (!((PetscObject)mc)->type_name) {
205: PetscCall(MatColoringSetType(mc, deft));
206: }
207: PetscCall(PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg));
208: if (flg) PetscCall(MatColoringSetDistance(mc, dist));
209: PetscCall(PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg));
210: if (flg) PetscCall(MatColoringSetMaxColors(mc, maxcolors));
211: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
212: PetscCall(PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL));
213: PetscCall(PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL));
214: PetscCall(PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL));
215: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject));
216: PetscOptionsEnd();
217: PetscFunctionReturn(PETSC_SUCCESS);
218: }
220: /*@
221: MatColoringSetDistance - Sets the distance of the coloring
223: Logically Collective
225: Input Parameters:
226: + mc - the `MatColoring` context
227: - dist - the distance the coloring should compute
229: Options Database Key:
230: . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
232: Level: beginner
234: Note:
235: The distance of the coloring denotes the minimum number
236: of edges in the graph induced by the matrix any two vertices
237: of the same color are. Distance-1 colorings are the classical
238: coloring, where no two vertices of the same color are adjacent.
239: distance-2 colorings are useful for the computation of Jacobians.
241: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
242: @*/
243: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
244: {
245: PetscFunctionBegin;
247: mc->dist = dist;
248: PetscFunctionReturn(PETSC_SUCCESS);
249: }
251: /*@
252: MatColoringGetDistance - Gets the distance of the coloring
254: Logically Collective
256: Input Parameter:
257: . mc - the `MatColoring` context
259: Output Parameter:
260: . dist - the current distance being used for the coloring.
262: Level: beginner
264: Note:
265: The distance of the coloring denotes the minimum number
266: of edges in the graph induced by the matrix any two vertices
267: of the same color are. Distance-1 colorings are the classical
268: coloring, where no two vertices of the same color are adjacent.
269: distance-2 colorings are useful for the computation of Jacobians.
271: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
272: @*/
273: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
274: {
275: PetscFunctionBegin;
277: if (dist) *dist = mc->dist;
278: PetscFunctionReturn(PETSC_SUCCESS);
279: }
281: /*@
282: MatColoringSetMaxColors - Sets the maximum number of colors to produce
284: Logically Collective
286: Input Parameters:
287: + mc - the `MatColoring` context
288: - maxcolors - the maximum number of colors to produce
290: Level: beginner
292: Notes:
293: Vertices not in an available color are set to have color maxcolors+1, which is not
294: a valid color as they may be adjacent.
296: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
298: This may be used to compute a certain number of
299: independent sets from the graph. For instance, while using
300: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
302: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
303: @*/
304: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
305: {
306: PetscFunctionBegin;
308: mc->maxcolors = maxcolors;
309: PetscFunctionReturn(PETSC_SUCCESS);
310: }
312: /*@
313: MatColoringGetMaxColors - Gets the maximum number of colors
315: Logically Collective
317: Input Parameter:
318: . mc - the `MatColoring` context
320: Output Parameter:
321: . maxcolors - the current maximum number of colors to produce
323: Level: beginner
325: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
326: @*/
327: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
328: {
329: PetscFunctionBegin;
331: if (maxcolors) *maxcolors = mc->maxcolors;
332: PetscFunctionReturn(PETSC_SUCCESS);
333: }
335: /*@
336: MatColoringApply - Apply the coloring to the matrix, producing index
337: sets corresponding to a number of independent sets in the induced
338: graph.
340: Collective
342: Input Parameter:
343: . mc - the `MatColoring` context
345: Output Parameter:
346: . coloring - the `ISColoring` instance containing the coloring
348: Level: beginner
350: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
351: @*/
352: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
353: {
354: PetscBool flg;
355: PetscViewerFormat format;
356: PetscViewer viewer;
357: PetscInt nc, ncolors;
359: PetscFunctionBegin;
361: PetscAssertPointer(coloring, 2);
362: PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
363: PetscUseTypeMethod(mc, apply, coloring);
364: PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));
366: /* valid */
367: if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
368: if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
370: /* view */
371: PetscCall(PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg));
372: if (flg && !PetscPreLoadingOn) {
373: PetscCall(PetscViewerPushFormat(viewer, format));
374: PetscCall(MatColoringView(mc, viewer));
375: PetscCall(MatGetSize(mc->mat, NULL, &nc));
376: PetscCall(ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL));
377: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors));
378: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc));
379: if (nc <= 1000) PetscCall(ISColoringView(*coloring, viewer));
380: PetscCall(PetscViewerPopFormat(viewer));
381: PetscCall(PetscOptionsRestoreViewer(&viewer));
382: }
383: PetscFunctionReturn(PETSC_SUCCESS);
384: }
386: /*@
387: MatColoringView - Output details about the `MatColoring`.
389: Collective
391: Input Parameters:
392: + mc - the `MatColoring` context
393: - viewer - the Viewer context
395: Level: beginner
397: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
398: @*/
399: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
400: {
401: PetscBool iascii;
403: PetscFunctionBegin;
405: if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
407: PetscCheckSameComm(mc, 1, viewer, 2);
409: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii));
410: if (iascii) {
411: PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
412: PetscCall(PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
413: if (mc->maxcolors > 0) {
414: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
415: } else {
416: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist));
417: }
418: }
419: PetscFunctionReturn(PETSC_SUCCESS);
420: }
422: /*@
423: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
425: Logically Collective
427: Input Parameters:
428: + mc - the `MatColoring` context
429: - wt - the weight type
431: Level: beginner
433: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
434: @*/
435: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
436: {
437: PetscFunctionBegin;
438: mc->weight_type = wt;
439: PetscFunctionReturn(PETSC_SUCCESS);
440: }