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 = MATCOLORINGSL;
188: char type[256];
189: PetscInt dist, maxcolors;
191: PetscFunctionBegin;
193: PetscCall(MatColoringGetDistance(mc, &dist));
194: if (dist == 2) deft = MATCOLORINGSL;
195: else deft = MATCOLORINGGREEDY;
196: PetscCall(MatColoringGetMaxColors(mc, &maxcolors));
197: PetscCall(MatColoringRegisterAll());
198: PetscObjectOptionsBegin((PetscObject)mc);
199: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
200: PetscCall(PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, 256, &flg));
201: if (flg) {
202: PetscCall(MatColoringSetType(mc, type));
203: } else if (!((PetscObject)mc)->type_name) {
204: PetscCall(MatColoringSetType(mc, deft));
205: }
206: PetscCall(PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg));
207: if (flg) PetscCall(MatColoringSetDistance(mc, dist));
208: PetscCall(PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg));
209: if (flg) PetscCall(MatColoringSetMaxColors(mc, maxcolors));
210: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
211: PetscCall(PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL));
212: PetscCall(PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL));
213: PetscCall(PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL));
214: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject));
215: PetscOptionsEnd();
216: PetscFunctionReturn(PETSC_SUCCESS);
217: }
219: /*@
220: MatColoringSetDistance - Sets the distance of the coloring
222: Logically Collective
224: Input Parameters:
225: + mc - the `MatColoring` context
226: - dist - the distance the coloring should compute
228: Options Database Key:
229: . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
231: Level: beginner
233: Note:
234: The distance of the coloring denotes the minimum number
235: of edges in the graph induced by the matrix any two vertices
236: of the same color are. Distance-1 colorings are the classical
237: coloring, where no two vertices of the same color are adjacent.
238: distance-2 colorings are useful for the computation of Jacobians.
240: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
241: @*/
242: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
243: {
244: PetscFunctionBegin;
246: mc->dist = dist;
247: PetscFunctionReturn(PETSC_SUCCESS);
248: }
250: /*@
251: MatColoringGetDistance - Gets the distance of the coloring
253: Logically Collective
255: Input Parameter:
256: . mc - the `MatColoring` context
258: Output Parameter:
259: . dist - the current distance being used for the coloring.
261: Level: beginner
263: Note:
264: The distance of the coloring denotes the minimum number
265: of edges in the graph induced by the matrix any two vertices
266: of the same color are. Distance-1 colorings are the classical
267: coloring, where no two vertices of the same color are adjacent.
268: distance-2 colorings are useful for the computation of Jacobians.
270: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
271: @*/
272: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
273: {
274: PetscFunctionBegin;
276: if (dist) *dist = mc->dist;
277: PetscFunctionReturn(PETSC_SUCCESS);
278: }
280: /*@
281: MatColoringSetMaxColors - Sets the maximum number of colors to produce
283: Logically Collective
285: Input Parameters:
286: + mc - the `MatColoring` context
287: - maxcolors - the maximum number of colors to produce
289: Level: beginner
291: Notes:
292: Vertices not in an available color are set to have color maxcolors+1, which is not
293: a valid color as they may be adjacent.
295: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
297: This may be used to compute a certain number of
298: independent sets from the graph. For instance, while using
299: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
301: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
302: @*/
303: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
304: {
305: PetscFunctionBegin;
307: mc->maxcolors = maxcolors;
308: PetscFunctionReturn(PETSC_SUCCESS);
309: }
311: /*@
312: MatColoringGetMaxColors - Gets the maximum number of colors
314: Logically Collective
316: Input Parameter:
317: . mc - the `MatColoring` context
319: Output Parameter:
320: . maxcolors - the current maximum number of colors to produce
322: Level: beginner
324: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
325: @*/
326: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
327: {
328: PetscFunctionBegin;
330: if (maxcolors) *maxcolors = mc->maxcolors;
331: PetscFunctionReturn(PETSC_SUCCESS);
332: }
334: /*@
335: MatColoringApply - Apply the coloring to the matrix, producing index
336: sets corresponding to a number of independent sets in the induced
337: graph.
339: Collective
341: Input Parameter:
342: . mc - the `MatColoring` context
344: Output Parameter:
345: . coloring - the `ISColoring` instance containing the coloring
347: Level: beginner
349: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
350: @*/
351: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
352: {
353: PetscBool flg;
354: PetscViewerFormat format;
355: PetscViewer viewer;
356: PetscInt nc, ncolors;
358: PetscFunctionBegin;
360: PetscAssertPointer(coloring, 2);
361: PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
362: PetscUseTypeMethod(mc, apply, coloring);
363: PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));
365: /* valid */
366: if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
367: if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
369: /* view */
370: PetscCall(PetscOptionsCreateViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg));
371: if (flg && !PetscPreLoadingOn) {
372: PetscCall(PetscViewerPushFormat(viewer, format));
373: PetscCall(MatColoringView(mc, viewer));
374: PetscCall(MatGetSize(mc->mat, NULL, &nc));
375: PetscCall(ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL));
376: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors));
377: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc));
378: if (nc <= 1000) PetscCall(ISColoringView(*coloring, viewer));
379: PetscCall(PetscViewerPopFormat(viewer));
380: PetscCall(PetscViewerDestroy(&viewer));
381: }
382: PetscFunctionReturn(PETSC_SUCCESS);
383: }
385: /*@
386: MatColoringView - Output details about the `MatColoring`.
388: Collective
390: Input Parameters:
391: + mc - the `MatColoring` context
392: - viewer - the Viewer context
394: Level: beginner
396: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
397: @*/
398: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
399: {
400: PetscBool iascii;
402: PetscFunctionBegin;
404: if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
406: PetscCheckSameComm(mc, 1, viewer, 2);
408: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii));
409: if (iascii) {
410: PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
411: PetscCall(PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
412: if (mc->maxcolors > 0) {
413: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
414: } else {
415: PetscCall(PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist));
416: }
417: }
418: PetscFunctionReturn(PETSC_SUCCESS);
419: }
421: /*@
422: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
424: Logically Collective
426: Input Parameters:
427: + mc - the `MatColoring` context
428: - wt - the weight type
430: Level: beginner
432: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
433: @*/
434: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
435: {
436: PetscFunctionBegin;
437: mc->weight_type = wt;
438: PetscFunctionReturn(PETSC_SUCCESS);
439: }