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
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 Sample usage:
19 .vb
20 MatColoringRegister("my_color",MyColor);
21 .ve
22
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
27
28 .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
29 @*/
MatColoringRegister(const char sname[],PetscErrorCode (* function)(MatColoring))30 PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
31 {
32 PetscErrorCode ierr;
33
34 PetscFunctionBegin;
35 ierr = MatInitializePackage();CHKERRQ(ierr);
36 ierr = PetscFunctionListAdd(&MatColoringList,sname,function);CHKERRQ(ierr);
37 PetscFunctionReturn(0);
38 }
39
40 /*@
41 MatColoringCreate - Creates a matrix coloring context.
42
43 Collective on MatColoring
44
45 Input Parameters:
46 . comm - MPI communicator
47
48 Output Parameter:
49 . mcptr - the new MatColoring context
50
51 Options Database Keys:
52 + -mat_coloring_type - the type of coloring algorithm used
53 . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
54 . -mat_coloring_distance - compute a distance 1,2,... coloring.
55 . -mat_coloring_view - print information about the coloring and the produced index sets
56 . -mat_coloring_test - debugging option that prints all coloring incompatibilities
57 - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
58
59 Level: beginner
60
61 Notes:
62 A distance one coloring is useful, for example, multi-color SOR. A distance two coloring is for the finite difference computation of Jacobians
63 (see MatFDColoringCreate()).
64
65 Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the MatColoring object or from the mesh from which the
66 matrix comes from with DMCreateColoring(). In general using the mesh produces a more optimal coloring (fewer colors).
67
68 Some coloring types only support distance two colorings
69
70 .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate(), DMCreateColoring()
71 @*/
MatColoringCreate(Mat m,MatColoring * mcptr)72 PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
73 {
74 MatColoring mc;
75 PetscErrorCode ierr;
76
77 PetscFunctionBegin;
78 PetscValidHeaderSpecific(m,MAT_CLASSID,1);
79 PetscValidPointer(mcptr,2);
80 *mcptr = NULL;
81
82 #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
83 ierr = MatInitializePackage();CHKERRQ(ierr);
84 #endif
85 ierr = PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);CHKERRQ(ierr);
86 ierr = PetscObjectReference((PetscObject)m);CHKERRQ(ierr);
87 mc->mat = m;
88 mc->dist = 2; /* default to Jacobian computation case */
89 mc->maxcolors = IS_COLORING_MAX;
90 *mcptr = mc;
91 mc->valid = PETSC_FALSE;
92 mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
93 mc->user_weights = NULL;
94 mc->user_lperm = NULL;
95 PetscFunctionReturn(0);
96 }
97
98
99 /*@
100 MatColoringDestroy - Destroys the matrix coloring context
101
102 Collective on MatColoring
103
104 Input Parameter:
105 . mc - the MatColoring context
106
107 Level: beginner
108
109 .seealso: MatColoringCreate(), MatColoringApply()
110 @*/
MatColoringDestroy(MatColoring * mc)111 PetscErrorCode MatColoringDestroy(MatColoring *mc)
112 {
113 PetscErrorCode ierr;
114
115 PetscFunctionBegin;
116 if (--((PetscObject)(*mc))->refct > 0) {*mc = NULL; PetscFunctionReturn(0);}
117 ierr = MatDestroy(&(*mc)->mat);CHKERRQ(ierr);
118 if ((*mc)->ops->destroy) {ierr = (*((*mc)->ops->destroy))(*mc);CHKERRQ(ierr);}
119 if ((*mc)->user_weights) {ierr = PetscFree((*mc)->user_weights);CHKERRQ(ierr);}
120 if ((*mc)->user_lperm) {ierr = PetscFree((*mc)->user_lperm);CHKERRQ(ierr);}
121 ierr = PetscHeaderDestroy(mc);CHKERRQ(ierr);
122 PetscFunctionReturn(0);
123 }
124
125 /*@C
126 MatColoringSetType - Sets the type of coloring algorithm used
127
128 Collective on MatColoring
129
130 Input Parameter:
131 + mc - the MatColoring context
132 - type - the type of coloring
133
134 Level: beginner
135
136 Notes:
137 Possible types include the sequential types MATCOLORINGLF,
138 MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
139 as a parallel MATCOLORINGMIS algorithm.
140
141 .seealso: MatColoringCreate(), MatColoringApply()
142 @*/
MatColoringSetType(MatColoring mc,MatColoringType type)143 PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
144 {
145 PetscBool match;
146 PetscErrorCode ierr,(*r)(MatColoring);
147
148 PetscFunctionBegin;
149 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
150 PetscValidCharPointer(type,2);
151 ierr = PetscObjectTypeCompare((PetscObject)mc,type,&match);CHKERRQ(ierr);
152 if (match) PetscFunctionReturn(0);
153 ierr = PetscFunctionListFind(MatColoringList,type,&r);CHKERRQ(ierr);
154 if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
155 if (mc->ops->destroy) {
156 ierr = (*(mc)->ops->destroy)(mc);CHKERRQ(ierr);
157 mc->ops->destroy = NULL;
158 }
159 mc->ops->apply = NULL;
160 mc->ops->view = NULL;
161 mc->ops->setfromoptions = NULL;
162 mc->ops->destroy = NULL;
163
164 ierr = PetscObjectChangeTypeName((PetscObject)mc,type);CHKERRQ(ierr);
165 ierr = (*r)(mc);CHKERRQ(ierr);
166 PetscFunctionReturn(0);
167 }
168
169 /*@
170 MatColoringSetFromOptions - Sets MatColoring options from user parameters
171
172 Collective on MatColoring
173
174 Input Parameters:
175 . mc - MatColoring context
176
177 Options Database Keys:
178 + -mat_coloring_type - the type of coloring algorithm used
179 . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
180 . -mat_coloring_distance - compute a distance 1,2,... coloring.
181 . -mat_coloring_view - print information about the coloring and the produced index sets
182 . -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
183 - -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)
184
185 Level: beginner
186
187 .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor()
188 @*/
MatColoringSetFromOptions(MatColoring mc)189 PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
190 {
191 PetscBool flg;
192 MatColoringType deft = MATCOLORINGSL;
193 char type[256];
194 PetscErrorCode ierr;
195 PetscInt dist,maxcolors;
196 PetscFunctionBegin;
197
198 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
199 ierr = MatColoringGetDistance(mc,&dist);CHKERRQ(ierr);
200 if (dist == 2) deft = MATCOLORINGSL;
201 else deft = MATCOLORINGGREEDY;
202 ierr = MatColoringGetMaxColors(mc,&maxcolors);CHKERRQ(ierr);
203 ierr = MatColoringRegisterAll();CHKERRQ(ierr);
204 ierr = PetscObjectOptionsBegin((PetscObject)mc);CHKERRQ(ierr);
205 if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
206 ierr = PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);CHKERRQ(ierr);
207 if (flg) {
208 ierr = MatColoringSetType(mc,type);CHKERRQ(ierr);
209 } else if (!((PetscObject)mc)->type_name) {
210 ierr = MatColoringSetType(mc,deft);CHKERRQ(ierr);
211 }
212 ierr = PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);CHKERRQ(ierr);
213 if (flg) {ierr = MatColoringSetDistance(mc,dist);CHKERRQ(ierr);}
214 ierr = PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);CHKERRQ(ierr);
215 if (flg) {ierr = MatColoringSetMaxColors(mc,maxcolors);CHKERRQ(ierr);}
216 if (mc->ops->setfromoptions) {
217 ierr = (*mc->ops->setfromoptions)(PetscOptionsObject,mc);CHKERRQ(ierr);
218 }
219 ierr = PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);CHKERRQ(ierr);
220 ierr = PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);CHKERRQ(ierr);
221 ierr = PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);CHKERRQ(ierr);
222 ierr = PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);CHKERRQ(ierr);
223 ierr = PetscOptionsEnd();CHKERRQ(ierr);
224 PetscFunctionReturn(0);
225 }
226
227 /*@
228 MatColoringSetDistance - Sets the distance of the coloring
229
230 Logically Collective on MatColoring
231
232 Input Parameters:
233 + mc - the MatColoring context
234 - dist - the distance the coloring should compute
235
236 Level: beginner
237
238 Notes:
239 The distance of the coloring denotes the minimum number
240 of edges in the graph induced by the matrix any two vertices
241 of the same color are. Distance-1 colorings are the classical
242 coloring, where no two vertices of the same color are adjacent.
243 distance-2 colorings are useful for the computation of Jacobians.
244
245 .seealso: MatColoringGetDistance(), MatColoringApply()
246 @*/
MatColoringSetDistance(MatColoring mc,PetscInt dist)247 PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
248 {
249 PetscFunctionBegin;
250 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
251 mc->dist = dist;
252 PetscFunctionReturn(0);
253 }
254
255 /*@
256 MatColoringGetDistance - Gets the distance of the coloring
257
258 Logically Collective on MatColoring
259
260 Input Parameter:
261 . mc - the MatColoring context
262
263 Output Parameter:
264 . dist - the current distance being used for the coloring.
265
266 Level: beginner
267
268 .seealso: MatColoringSetDistance(), MatColoringApply()
269 @*/
MatColoringGetDistance(MatColoring mc,PetscInt * dist)270 PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
271 {
272 PetscFunctionBegin;
273 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
274 if (dist) *dist = mc->dist;
275 PetscFunctionReturn(0);
276 }
277
278 /*@
279 MatColoringSetMaxColors - Sets the maximum number of colors
280
281 Logically Collective on MatColoring
282
283 Input Parameter:
284 + mc - the MatColoring context
285 - maxcolors - the maximum number of colors to produce
286
287 Level: beginner
288
289 Notes:
290 This may be used to compute a certain number of
291 independent sets from the graph. For instance, while using
292 MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
293 not in a color are set to have color maxcolors+1, which is not
294 a valid color as they may be adjacent.
295
296 .seealso: MatColoringGetMaxColors(), MatColoringApply()
297 @*/
MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)298 PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
299 {
300 PetscFunctionBegin;
301 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
302 mc->maxcolors = maxcolors;
303 PetscFunctionReturn(0);
304 }
305
306 /*@
307 MatColoringGetMaxColors - Gets the maximum number of colors
308
309 Logically Collective on MatColoring
310
311 Input Parameter:
312 . mc - the MatColoring context
313
314 Output Parameter:
315 . maxcolors - the current maximum number of colors to produce
316
317 Level: beginner
318
319 .seealso: MatColoringSetMaxColors(), MatColoringApply()
320 @*/
MatColoringGetMaxColors(MatColoring mc,PetscInt * maxcolors)321 PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
322 {
323 PetscFunctionBegin;
324 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
325 if (maxcolors) *maxcolors = mc->maxcolors;
326 PetscFunctionReturn(0);
327 }
328
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.
333
334 Collective on MatColoring
335
336 Input Parameters:
337 . mc - the MatColoring context
338
339 Output Parameter:
340 . coloring - the ISColoring instance containing the coloring
341
342 Level: beginner
343
344 .seealso: MatColoring, MatColoringCreate()
345 @*/
MatColoringApply(MatColoring mc,ISColoring * coloring)346 PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
347 {
348 PetscErrorCode ierr;
349 PetscBool flg;
350 PetscViewerFormat format;
351 PetscViewer viewer;
352 PetscInt nc,ncolors;
353
354 PetscFunctionBegin;
355 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
356 ierr = PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);CHKERRQ(ierr);
357 ierr = (*mc->ops->apply)(mc,coloring);CHKERRQ(ierr);
358 ierr = PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);CHKERRQ(ierr);
359
360 /* valid */
361 if (mc->valid) {
362 ierr = MatColoringTest(mc,*coloring);CHKERRQ(ierr);
363 }
364 if (mc->valid_iscoloring) {
365 ierr = MatISColoringTest(mc->mat,*coloring);CHKERRQ(ierr);
366 }
367
368 /* view */
369 ierr = PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);CHKERRQ(ierr);
370 if (flg && !PetscPreLoadingOn) {
371 ierr = PetscViewerPushFormat(viewer,format);CHKERRQ(ierr);
372 ierr = MatColoringView(mc,viewer);CHKERRQ(ierr);
373 ierr = MatGetSize(mc->mat,NULL,&nc);CHKERRQ(ierr);
374 ierr = ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);CHKERRQ(ierr);
375 ierr = PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);CHKERRQ(ierr);
376 ierr = PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);CHKERRQ(ierr);
377 if (nc <= 1000) {ierr = ISColoringView(*coloring,viewer);CHKERRQ(ierr);}
378 ierr = PetscViewerPopFormat(viewer);CHKERRQ(ierr);
379 ierr = PetscViewerDestroy(&viewer);CHKERRQ(ierr);
380 }
381 PetscFunctionReturn(0);
382 }
383
384 /*@
385 MatColoringView - Output details about the MatColoring.
386
387 Collective on MatColoring
388
389 Input Parameters:
390 - mc - the MatColoring context
391 + viewer - the Viewer context
392
393 Level: beginner
394
395 .seealso: MatColoring, MatColoringApply()
396 @*/
MatColoringView(MatColoring mc,PetscViewer viewer)397 PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
398 {
399 PetscErrorCode ierr;
400 PetscBool iascii;
401
402 PetscFunctionBegin;
403 PetscValidHeaderSpecific(mc,MAT_COLORING_CLASSID,1);
404 if (!viewer) {
405 ierr = PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);CHKERRQ(ierr);
406 }
407 PetscValidHeaderSpecific(viewer,PETSC_VIEWER_CLASSID,2);
408 PetscCheckSameComm(mc,1,viewer,2);
409
410 ierr = PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);CHKERRQ(ierr);
411 if (iascii) {
412 ierr = PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);CHKERRQ(ierr);
413 ierr = PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);CHKERRQ(ierr);
414 if (mc->maxcolors > 0) {
415 ierr = PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);CHKERRQ(ierr);
416 } else {
417 ierr = PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);CHKERRQ(ierr);
418 }
419 }
420 PetscFunctionReturn(0);
421 }
422
423 /*@
424 MatColoringSetWeightType - Set the type of weight computation used.
425
426 Logically collective on MatColoring
427
428 Input Parameters:
429 - mc - the MatColoring context
430 + wt - the weight type
431
432 Level: beginner
433
434 .seealso: MatColoring, MatColoringWeightType
435 @*/
MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)436 PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
437 {
438 PetscFunctionBegin;
439 mc->weight_type = wt;
440 PetscFunctionReturn(0);
441
442 }
443