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: Sample 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: MatInitializePackage();
33: PetscFunctionListAdd(&MatColoringList, sname, function);
34: return 0;
35: }
37: /*@
38: MatColoringCreate - Creates a matrix coloring context.
40: Collective
42: Input Parameters:
43: . comm - MPI communicator
45: Output Parameter:
46: . mcptr - the new `MatColoring` context
48: Options Database Keys:
49: + -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
50: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
51: . -mat_coloring_distance - compute a distance 1,2,... coloring.
52: . -mat_coloring_view - print information about the coloring and the produced index sets
53: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
54: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
56: Level: beginner
58: Notes:
59: A distance one coloring is useful, for example, multi-color SOR.
61: A distance two coloring is for the finite difference computation of Jacobians (see `MatFDColoringCreate())`.
63: Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the `MatColoring` object or from the mesh from which the
64: matrix comes from with `DMCreateColoring()`. In general using the mesh produces a more optimal coloring (fewer colors).
66: Some coloring types only support distance two colorings
68: .seealso: `MatColoringSetFromOptions()`, `MatColoring`, `MatColoringApply()`, `MatFDColoringCreate()`, `DMCreateColoring()`, `MatColoringType`
69: @*/
70: PetscErrorCode MatColoringCreate(Mat m, MatColoring *mcptr)
71: {
72: MatColoring mc;
76: *mcptr = NULL;
78: MatInitializePackage();
79: PetscHeaderCreate(mc, MAT_COLORING_CLASSID, "MatColoring", "Matrix coloring", "MatColoring", PetscObjectComm((PetscObject)m), MatColoringDestroy, MatColoringView);
80: 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: return 0;
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: if (--((PetscObject)(*mc))->refct > 0) {
107: *mc = NULL;
108: return 0;
109: }
110: MatDestroy(&(*mc)->mat);
111: if ((*mc)->ops->destroy) (*((*mc)->ops->destroy))(*mc);
112: if ((*mc)->user_weights) PetscFree((*mc)->user_weights);
113: if ((*mc)->user_lperm) PetscFree((*mc)->user_lperm);
114: PetscHeaderDestroy(mc);
115: return 0;
116: }
118: /*@C
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);
146: PetscObjectTypeCompare((PetscObject)mc, type, &match);
147: if (match) return 0;
148: PetscFunctionListFind(MatColoringList, type, &r);
150: if (mc->ops->destroy) {
151: (*(mc)->ops->destroy)(mc);
152: mc->ops->destroy = NULL;
153: }
154: mc->ops->apply = NULL;
155: mc->ops->view = NULL;
156: mc->ops->setfromoptions = NULL;
157: mc->ops->destroy = NULL;
159: PetscObjectChangeTypeName((PetscObject)mc, type);
160: (*r)(mc);
161: return 0;
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;
192: MatColoringGetDistance(mc, &dist);
193: if (dist == 2) deft = MATCOLORINGSL;
194: else deft = MATCOLORINGGREEDY;
195: MatColoringGetMaxColors(mc, &maxcolors);
196: MatColoringRegisterAll();
197: PetscObjectOptionsBegin((PetscObject)mc);
198: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
199: PetscOptionsFList("-mat_coloring_type", "The coloring method used", "MatColoringSetType", MatColoringList, deft, type, 256, &flg);
200: if (flg) {
201: MatColoringSetType(mc, type);
202: } else if (!((PetscObject)mc)->type_name) {
203: MatColoringSetType(mc, deft);
204: }
205: PetscOptionsInt("-mat_coloring_distance", "Distance of the coloring", "MatColoringSetDistance", dist, &dist, &flg);
206: if (flg) MatColoringSetDistance(mc, dist);
207: PetscOptionsInt("-mat_coloring_maxcolors", "Maximum colors returned at the end. 1 returns an independent set", "MatColoringSetMaxColors", maxcolors, &maxcolors, &flg);
208: if (flg) MatColoringSetMaxColors(mc, maxcolors);
209: PetscTryTypeMethod(mc, setfromoptions, PetscOptionsObject);
210: PetscOptionsBool("-mat_coloring_test", "Check that a valid coloring has been produced", "", mc->valid, &mc->valid, NULL);
211: PetscOptionsBool("-mat_is_coloring_test", "Check that a valid iscoloring has been produced", "", mc->valid_iscoloring, &mc->valid_iscoloring, NULL);
212: PetscOptionsEnum("-mat_coloring_weight_type", "Sets the type of vertex weighting used", "MatColoringSetWeightType", MatColoringWeightTypes, (PetscEnum)mc->weight_type, (PetscEnum *)&mc->weight_type, NULL);
213: PetscObjectProcessOptionsHandlers((PetscObject)mc, PetscOptionsObject);
214: PetscOptionsEnd();
215: return 0;
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: {
244: mc->dist = dist;
245: return 0;
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: {
273: if (dist) *dist = mc->dist;
274: return 0;
275: }
277: /*@
278: MatColoringSetMaxColors - Sets the maximum number of colors to produce
280: Logically Collective
282: Input Parameters:
283: + mc - the `MatColoring` context
284: - maxcolors - the maximum number of colors to produce
286: Level: beginner
288: Notes:
289: Vertices not in an available color are set to have color maxcolors+1, which is not
290: a valid color as they may be adjacent.
292: This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
294: This may be used to compute a certain number of
295: independent sets from the graph. For instance, while using
296: `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.
298: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
299: @*/
300: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
301: {
303: mc->maxcolors = maxcolors;
304: return 0;
305: }
307: /*@
308: MatColoringGetMaxColors - Gets the maximum number of colors
310: Logically Collective
312: Input Parameter:
313: . mc - the `MatColoring` context
315: Output Parameter:
316: . maxcolors - the current maximum number of colors to produce
318: Level: beginner
320: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
321: @*/
322: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
323: {
325: if (maxcolors) *maxcolors = mc->maxcolors;
326: return 0;
327: }
329: /*@
330: MatColoringApply - Apply the coloring to the matrix, producing index
331: sets corresponding to a number of independent sets in the induced
332: graph.
334: Collective
336: Input Parameters:
337: . mc - the `MatColoring` context
339: Output Parameter:
340: . coloring - the `ISColoring` instance containing the coloring
342: Level: beginner
344: .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
345: @*/
346: PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
347: {
348: PetscBool flg;
349: PetscViewerFormat format;
350: PetscViewer viewer;
351: PetscInt nc, ncolors;
355: PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0);
356: PetscUseTypeMethod(mc, apply, coloring);
357: PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0);
359: /* valid */
360: if (mc->valid) MatColoringTest(mc, *coloring);
361: if (mc->valid_iscoloring) MatISColoringTest(mc->mat, *coloring);
363: /* view */
364: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc), ((PetscObject)mc)->options, ((PetscObject)mc)->prefix, "-mat_coloring_view", &viewer, &format, &flg);
365: if (flg && !PetscPreLoadingOn) {
366: PetscViewerPushFormat(viewer, format);
367: MatColoringView(mc, viewer);
368: MatGetSize(mc->mat, NULL, &nc);
369: ISColoringGetIS(*coloring, PETSC_USE_POINTER, &ncolors, NULL);
370: PetscViewerASCIIPrintf(viewer, " Number of colors %" PetscInt_FMT "\n", ncolors);
371: PetscViewerASCIIPrintf(viewer, " Number of total columns %" PetscInt_FMT "\n", nc);
372: if (nc <= 1000) ISColoringView(*coloring, viewer);
373: PetscViewerPopFormat(viewer);
374: PetscViewerDestroy(&viewer);
375: }
376: return 0;
377: }
379: /*@
380: MatColoringView - Output details about the `MatColoring`.
382: Collective
384: Input Parameters:
385: - mc - the `MatColoring` context
386: + viewer - the Viewer context
388: Level: beginner
390: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
391: @*/
392: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
393: {
394: PetscBool iascii;
397: if (!viewer) PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer);
401: PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii);
402: if (iascii) {
403: PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer);
404: PetscViewerASCIIPrintf(viewer, " Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]);
405: if (mc->maxcolors > 0) {
406: PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors);
407: } else {
408: PetscViewerASCIIPrintf(viewer, " Distance %" PetscInt_FMT "\n", mc->dist);
409: }
410: }
411: return 0;
412: }
414: /*@
415: MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
417: Logically collective
419: Input Parameters:
420: - mc - the `MatColoring` context
421: + wt - the weight type
423: Level: beginner
425: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
426: @*/
427: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
428: {
429: mc->weight_type = wt;
430: return 0;
431: }