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: 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(PetscFree((*mc)->user_weights));
113: PetscCall(PetscFree((*mc)->user_lperm));
114: PetscCall(PetscHeaderDestroy(mc));
115: PetscFunctionReturn(PETSC_SUCCESS);
116: }
118: /*@
119: MatColoringSetType - Sets the type of coloring algorithm used
121: Collective
123: Input Parameters:
124: + mc - the `MatColoring` context
125: - type - the type of coloring
127: Options Database Key:
128: . -mat_coloring_type type - the name of the type
130: Level: beginner
132: Note:
133: Possible types include the sequential types `MATCOLORINGLF`,
134: `MATCOLORINGSL`, and `MATCOLORINGID` from the MINPACK package as well
135: as a parallel `MATCOLORINGGREEDY` algorithm.
137: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringType`, `MatColoringCreate()`, `MatColoringApply()`
138: @*/
139: PetscErrorCode MatColoringSetType(MatColoring mc, MatColoringType type)
140: {
141: PetscBool match;
142: PetscErrorCode (*r)(MatColoring);
144: PetscFunctionBegin;
146: PetscAssertPointer(type, 2);
147: PetscCall(PetscObjectTypeCompare((PetscObject)mc, type, &match));
148: if (match) PetscFunctionReturn(PETSC_SUCCESS);
149: PetscCall(PetscFunctionListFind(MatColoringList, type, &r));
150: PetscCheck(r, PetscObjectComm((PetscObject)mc), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unable to find requested MatColoring type %s", type);
152: PetscTryTypeMethod(mc, destroy);
153: mc->ops->destroy = NULL;
154: mc->ops->apply = NULL;
155: mc->ops->view = NULL;
156: mc->ops->setfromoptions = NULL;
157: mc->ops->destroy = NULL;
159: PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
160: PetscCall((*r)(mc));
161: PetscFunctionReturn(PETSC_SUCCESS);
162: }
164: /*@
165: MatColoringSetFromOptions - Sets `MatColoring` options from options database
167: Collective
169: Input Parameter:
170: . mc - `MatColoring` context
172: Options Database Keys:
173: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
174: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
175: . -mat_coloring_distance - compute a distance 1,2,... coloring.
176: . -mat_coloring_view - print information about the coloring and the produced index sets
177: . -snes_fd_color - instruct SNES to using coloring and then `MatFDColoring` to compute the Jacobians
178: - -snes_fd_color_use_mat - instruct `SNES` to color the matrix directly instead of the `DM` from which the matrix comes (the default)
180: Level: beginner
182: .seealso: `MatColoring`, `MatColoringApply()`, `MatColoringSetDistance()`, `MatColoringSetType()`, `SNESComputeJacobianDefaultColor()`, `MatColoringType`
183: @*/
184: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
185: {
186: PetscBool flg;
187: MatColoringType deft = MATCOLORINGGREEDY;
188: char type[256];
189: PetscInt dist, maxcolors;
191: PetscFunctionBegin;
193: PetscCall(MatColoringGetDistance(mc, &dist));
194: if (dist == 2) deft = MATCOLORINGSL;
195: PetscCall(MatColoringGetMaxColors(mc, &maxcolors));
196: PetscCall(MatColoringRegisterAll());
197: PetscObjectOptionsBegin((PetscObject)mc);
198: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
199: PetscCall(PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, 256, &flg));
200: if (flg) {
201: PetscCall(MatColoringSetType(mc, type));
202: } else if (!((PetscObject)mc)->type_name) {
203: PetscCall(MatColoringSetType(mc, deft));
204: }
205: PetscCall(PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg));
206: if (flg) PetscCall(MatColoringSetDistance(mc, dist));
207: PetscCall(PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg));
208: if (flg) PetscCall(MatColoringSetMaxColors(mc, maxcolors));
209: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
210: PetscCall(PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL));
211: PetscCall(PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL));
212: PetscCall(PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL));
213: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject));
214: PetscOptionsEnd();
215: PetscFunctionReturn(PETSC_SUCCESS);
216: }
218: /*@
219: MatColoringSetDistance - Sets the distance of the coloring
221: Logically Collective
223: Input Parameters:
224: + mc - the `MatColoring` context
225: - dist - the distance the coloring should compute
227: Options Database Key:
228: . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
230: Level: beginner
232: Note:
233: The distance of the coloring denotes the minimum number
234: of edges in the graph induced by the matrix any two vertices
235: of the same color are. Distance-1 colorings are the classical
236: coloring, where no two vertices of the same color are adjacent.
237: distance-2 colorings are useful for the computation of Jacobians.
239: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
240: @*/
241: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
242: {
243: PetscFunctionBegin;
245: mc->dist = dist;
246: PetscFunctionReturn(PETSC_SUCCESS);
247: }
249: /*@
250: MatColoringGetDistance - Gets the distance of the coloring
252: Logically Collective
254: Input Parameter:
255: . mc - the `MatColoring` context
257: Output Parameter:
258: . dist - the current distance being used for the coloring.
260: Level: beginner
262: Note:
263: The distance of the coloring denotes the minimum number
264: of edges in the graph induced by the matrix any two vertices
265: of the same color are. Distance-1 colorings are the classical
266: coloring, where no two vertices of the same color are adjacent.
267: distance-2 colorings are useful for the computation of Jacobians.
269: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
270: @*/
271: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
272: {
273: PetscFunctionBegin;
275: if (dist) *dist = mc->dist;
276: PetscFunctionReturn(PETSC_SUCCESS);
277: }
279: /*@
280: MatColoringSetMaxColors - Sets the maximum number of colors to produce
282: Logically Collective
284: Input Parameters:
285: + mc - the `MatColoring` context
286: - maxcolors - the maximum number of colors to produce
288: Level: beginner
290: Notes:
291: Vertices not in an available color are set to have color maxcolors+1, which is not
292: a valid color as they may be adjacent.
294: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
296: This may be used to compute a certain number of
297: independent sets from the graph. For instance, while using
298: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
300: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
301: @*/
302: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
303: {
304: PetscFunctionBegin;
306: mc->maxcolors = maxcolors;
307: PetscFunctionReturn(PETSC_SUCCESS);
308: }
310: /*@
311: MatColoringGetMaxColors - Gets the maximum number of colors
313: Logically Collective
315: Input Parameter:
316: . mc - the `MatColoring` context
318: Output Parameter:
319: . maxcolors - the current maximum number of colors to produce
321: Level: beginner
323: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
324: @*/
325: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
326: {
327: PetscFunctionBegin;
329: if (maxcolors) *maxcolors = mc->maxcolors;
330: PetscFunctionReturn(PETSC_SUCCESS);
331: }
333: /*@
334: MatColoringApply - Apply the coloring to the matrix, producing index
335: sets corresponding to a number of independent sets in the induced
336: graph.
338: Collective
340: Input Parameter:
341: . mc - the `MatColoring` context
343: Output Parameter:
344: . coloring - the `ISColoring` instance containing the coloring
346: Level: beginner
348: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
349: @*/
350: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
351: {
352: PetscBool flg;
353: PetscViewerFormat format;
354: PetscViewer viewer;
355: PetscInt nc, ncolors;
357: PetscFunctionBegin;
359: PetscAssertPointer(coloring, 2);
360: PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
361: PetscUseTypeMethod(mc, apply, coloring);
362: PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));
364: /* valid */
365: if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
366: if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
368: /* view */
369: PetscCall(PetscOptionsCreateViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg));
370: if (flg && !PetscPreLoadingOn) {
371: PetscCall(PetscViewerPushFormat(viewer, format));
372: PetscCall(MatColoringView(mc, viewer));
373: PetscCall(MatGetSize(mc->mat, NULL, &nc));
374: PetscCall(ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL));
375: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors));
376: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc));
377: if (nc <= 1000) PetscCall(ISColoringView(*coloring, viewer));
378: PetscCall(PetscViewerPopFormat(viewer));
379: PetscCall(PetscViewerDestroy(&viewer));
380: }
381: PetscFunctionReturn(PETSC_SUCCESS);
382: }
384: /*@
385: MatColoringView - Output details about the `MatColoring`.
387: Collective
389: Input Parameters:
390: + mc - the `MatColoring` context
391: - viewer - the Viewer context
393: Level: beginner
395: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
396: @*/
397: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
398: {
399: PetscBool iascii;
401: PetscFunctionBegin;
403: if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
405: PetscCheckSameComm(mc, 1, viewer, 2);
407: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii));
408: if (iascii) {
409: PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
410: PetscCall(PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
411: if (mc->maxcolors > 0) {
412: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
413: } else {
414: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist));
415: }
416: }
417: PetscFunctionReturn(PETSC_SUCCESS);
418: }
420: /*@
421: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
423: Logically Collective
425: Input Parameters:
426: + mc - the `MatColoring` context
427: - wt - the weight type
429: Level: beginner
431: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
432: @*/
433: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
434: {
435: PetscFunctionBegin;
436: mc->weight_type = wt;
437: PetscFunctionReturn(PETSC_SUCCESS);
438: }