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