1 #include <petsc/private/matimpl.h> /*I "petscmat.h" I*/
2
3 PetscFunctionList MatColoringList = NULL;
4 PetscBool MatColoringRegisterAllCalled = PETSC_FALSE;
5 const char *const MatColoringWeightTypes[] = {"RANDOM", "LEXICAL", "LF", "SL", "MatColoringWeightType", "MAT_COLORING_WEIGHT_", NULL};
6
7 /*@C
8 MatColoringRegister - Adds a new sparse matrix coloring to the matrix package.
9
10 Not Collective, No Fortran Support
11
12 Input Parameters:
13 + sname - name of Coloring (for example `MATCOLORINGSL`)
14 - function - function pointer that creates the coloring
15
16 Level: developer
17
18 Example Usage:
19 .vb
20 MatColoringRegister("my_color", MyColor);
21 .ve
22
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`
25
26 .seealso: `MatColoringType`, `MatColoringRegisterDestroy()`, `MatColoringRegisterAll()`
27 @*/
MatColoringRegister(const char sname[],PetscErrorCode (* function)(MatColoring))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 }
35
36 /*@
37 MatColoringCreate - Creates a matrix coloring context.
38
39 Collective
40
41 Input Parameter:
42 . m - a `Mat` from which a coloring is derived
43
44 Output Parameter:
45 . mcptr - the new `MatColoring` context
46
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
54
55 Level: beginner
56
57 Notes:
58 A distance one coloring is useful, for example, multi-color SOR.
59
60 A distance two coloring is for the finite difference computation of Jacobians (see `MatFDColoringCreate()`).
61
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).
64
65 Some coloring types only support distance two colorings
66
67 .seealso: `MatColoringSetFromOptions()`, `MatColoring`, `MatColoringApply()`, `MatFDColoringCreate()`, `DMCreateColoring()`, `MatColoringType`
68 @*/
MatColoringCreate(Mat m,MatColoring * mcptr)69 PetscErrorCode MatColoringCreate(Mat m, MatColoring *mcptr)
70 {
71 MatColoring mc;
72
73 PetscFunctionBegin;
74 PetscValidHeaderSpecific(m, MAT_CLASSID, 1);
75 PetscAssertPointer(mcptr, 2);
76 PetscCall(MatInitializePackage());
77
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 }
90
91 /*@
92 MatColoringDestroy - Destroys the matrix coloring context
93
94 Collective
95
96 Input Parameter:
97 . mc - the `MatColoring` context
98
99 Level: beginner
100
101 .seealso: `MatColoring`, `MatColoringCreate()`, `MatColoringApply()`
102 @*/
MatColoringDestroy(MatColoring * mc)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 }
117
118 /*@
119 MatColoringSetType - Sets the type of coloring algorithm used
120
121 Collective
122
123 Input Parameters:
124 + mc - the `MatColoring` context
125 - type - the type of coloring
126
127 Options Database Key:
128 . -mat_coloring_type type - the name of the type
129
130 Level: beginner
131
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.
136
137 .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringType`, `MatColoringCreate()`, `MatColoringApply()`
138 @*/
MatColoringSetType(MatColoring mc,MatColoringType type)139 PetscErrorCode MatColoringSetType(MatColoring mc, MatColoringType type)
140 {
141 PetscBool match;
142 PetscErrorCode (*r)(MatColoring);
143
144 PetscFunctionBegin;
145 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
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);
151
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;
158
159 PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
160 PetscCall((*r)(mc));
161 PetscFunctionReturn(PETSC_SUCCESS);
162 }
163
164 /*@
165 MatColoringSetFromOptions - Sets `MatColoring` options from options database
166
167 Collective
168
169 Input Parameter:
170 . mc - `MatColoring` context
171
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)
179
180 Level: beginner
181
182 .seealso: `MatColoring`, `MatColoringApply()`, `MatColoringSetDistance()`, `MatColoringSetType()`, `SNESComputeJacobianDefaultColor()`, `MatColoringType`
183 @*/
MatColoringSetFromOptions(MatColoring mc)184 PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
185 {
186 PetscBool flg;
187 MatColoringType deft = MATCOLORINGGREEDY;
188 char type[256];
189 PetscInt dist, maxcolors;
190
191 PetscFunctionBegin;
192 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
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 }
217
218 /*@
219 MatColoringSetDistance - Sets the distance of the coloring
220
221 Logically Collective
222
223 Input Parameters:
224 + mc - the `MatColoring` context
225 - dist - the distance the coloring should compute
226
227 Options Database Key:
228 . -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.
229
230 Level: beginner
231
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.
238
239 .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
240 @*/
MatColoringSetDistance(MatColoring mc,PetscInt dist)241 PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
242 {
243 PetscFunctionBegin;
244 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
245 mc->dist = dist;
246 PetscFunctionReturn(PETSC_SUCCESS);
247 }
248
249 /*@
250 MatColoringGetDistance - Gets the distance of the coloring
251
252 Logically Collective
253
254 Input Parameter:
255 . mc - the `MatColoring` context
256
257 Output Parameter:
258 . dist - the current distance being used for the coloring.
259
260 Level: beginner
261
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.
268
269 .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
270 @*/
MatColoringGetDistance(MatColoring mc,PetscInt * dist)271 PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
272 {
273 PetscFunctionBegin;
274 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
275 if (dist) *dist = mc->dist;
276 PetscFunctionReturn(PETSC_SUCCESS);
277 }
278
279 /*@
280 MatColoringSetMaxColors - Sets the maximum number of colors to produce
281
282 Logically Collective
283
284 Input Parameters:
285 + mc - the `MatColoring` context
286 - maxcolors - the maximum number of colors to produce
287
288 Level: beginner
289
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.
293
294 This works only for `MATCOLORINGGREEDY` and `MATCOLORINGJP`
295
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.
299
300 .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
301 @*/
MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)302 PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
303 {
304 PetscFunctionBegin;
305 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
306 mc->maxcolors = maxcolors;
307 PetscFunctionReturn(PETSC_SUCCESS);
308 }
309
310 /*@
311 MatColoringGetMaxColors - Gets the maximum number of colors
312
313 Logically Collective
314
315 Input Parameter:
316 . mc - the `MatColoring` context
317
318 Output Parameter:
319 . maxcolors - the current maximum number of colors to produce
320
321 Level: beginner
322
323 .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
324 @*/
MatColoringGetMaxColors(MatColoring mc,PetscInt * maxcolors)325 PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
326 {
327 PetscFunctionBegin;
328 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
329 if (maxcolors) *maxcolors = mc->maxcolors;
330 PetscFunctionReturn(PETSC_SUCCESS);
331 }
332
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.
337
338 Collective
339
340 Input Parameter:
341 . mc - the `MatColoring` context
342
343 Output Parameter:
344 . coloring - the `ISColoring` instance containing the coloring
345
346 Level: beginner
347
348 .seealso: `ISColoring`, `MatColoring`, `MatColoringCreate()`
349 @*/
MatColoringApply(MatColoring mc,ISColoring * coloring)350 PetscErrorCode MatColoringApply(MatColoring mc, ISColoring *coloring)
351 {
352 PetscBool flg;
353 PetscViewerFormat format;
354 PetscViewer viewer;
355 PetscInt nc, ncolors;
356
357 PetscFunctionBegin;
358 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
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));
363
364 /* valid */
365 if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
366 if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));
367
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 }
383
384 /*@
385 MatColoringView - Output details about the `MatColoring`.
386
387 Collective
388
389 Input Parameters:
390 + mc - the `MatColoring` context
391 - viewer - the Viewer context
392
393 Level: beginner
394
395 .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
396 @*/
MatColoringView(MatColoring mc,PetscViewer viewer)397 PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
398 {
399 PetscBool isascii;
400
401 PetscFunctionBegin;
402 PetscValidHeaderSpecific(mc, MAT_COLORING_CLASSID, 1);
403 if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
404 PetscValidHeaderSpecific(viewer, PETSC_VIEWER_CLASSID, 2);
405 PetscCheckSameComm(mc, 1, viewer, 2);
406
407 PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
408 if (isascii) {
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 }
419
420 /*@
421 MatColoringSetWeightType - Set the type of weight computation used while computing the coloring
422
423 Logically Collective
424
425 Input Parameters:
426 + mc - the `MatColoring` context
427 - wt - the weight type
428
429 Level: beginner
430
431 .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
432 @*/
MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)433 PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
434 {
435 PetscFunctionBegin;
436 mc->weight_type = wt;
437 PetscFunctionReturn(PETSC_SUCCESS);
438 }
439