Actual source code: matcoloring.c

petsc-main 2021-04-20
Report Typos and Errors
  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: MatColoringRegisterDestroy(), MatColoringRegisterAll()
 29: @*/
 30: PetscErrorCode  MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
 31: {

 35:   MatInitializePackage();
 36:   PetscFunctionListAdd(&MatColoringList,sname,function);
 37:   return(0);
 38: }

 40: /*@
 41:    MatColoringCreate - Creates a matrix coloring context.

 43:    Collective on MatColoring

 45:    Input Parameters:
 46: .  comm - MPI communicator

 48:    Output Parameter:
 49: .  mcptr - the new MatColoring context

 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

 59:    Level: beginner

 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()).

 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).

 68:           Some coloring types only support distance two colorings

 70: .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate(), DMCreateColoring()
 71: @*/
 72: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
 73: {
 74:   MatColoring    mc;

 80:   *mcptr = NULL;

 82:   MatInitializePackage();
 83:   PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
 84:   PetscObjectReference((PetscObject)m);
 85:   mc->mat       = m;
 86:   mc->dist      = 2; /* default to Jacobian computation case */
 87:   mc->maxcolors = IS_COLORING_MAX;
 88:   *mcptr        = mc;
 89:   mc->valid     = PETSC_FALSE;
 90:   mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
 91:   mc->user_weights = NULL;
 92:   mc->user_lperm = NULL;
 93:   return(0);
 94: }


 97: /*@
 98:    MatColoringDestroy - Destroys the matrix coloring context

100:    Collective on MatColoring

102:    Input Parameter:
103: .  mc - the MatColoring context

105:    Level: beginner

107: .seealso: MatColoringCreate(), MatColoringApply()
108: @*/
109: PetscErrorCode MatColoringDestroy(MatColoring *mc)
110: {

114:   if (--((PetscObject)(*mc))->refct > 0) {*mc = NULL; return(0);}
115:   MatDestroy(&(*mc)->mat);
116:   if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
117:   if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
118:   if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
119:   PetscHeaderDestroy(mc);
120:   return(0);
121: }

123: /*@C
124:    MatColoringSetType - Sets the type of coloring algorithm used

126:    Collective on MatColoring

128:    Input Parameter:
129: +  mc - the MatColoring context
130: -  type - the type of coloring

132:    Level: beginner

134:    Notes:
135:     Possible types include the sequential types MATCOLORINGLF,
136:    MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
137:    as a parallel MATCOLORINGMIS algorithm.

139: .seealso: MatColoringCreate(), MatColoringApply()
140: @*/
141: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
142: {
143:   PetscBool      match;
144:   PetscErrorCode ierr,(*r)(MatColoring);

149:   PetscObjectTypeCompare((PetscObject)mc,type,&match);
150:   if (match) return(0);
151:    PetscFunctionListFind(MatColoringList,type,&r);
152:   if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
153:   if (mc->ops->destroy) {
154:     (*(mc)->ops->destroy)(mc);
155:     mc->ops->destroy = NULL;
156:   }
157:   mc->ops->apply            = NULL;
158:   mc->ops->view             = NULL;
159:   mc->ops->setfromoptions   = NULL;
160:   mc->ops->destroy          = NULL;

162:   PetscObjectChangeTypeName((PetscObject)mc,type);
163:   (*r)(mc);
164:   return(0);
165: }

167: /*@
168:    MatColoringSetFromOptions - Sets MatColoring options from user parameters

170:    Collective on MatColoring

172:    Input Parameters:
173: .  mc - MatColoring context

175:    Options Database Keys:
176: +   -mat_coloring_type - the type of coloring algorithm used
177: .   -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
178: .   -mat_coloring_distance - compute a distance 1,2,... coloring.
179: .   -mat_coloring_view - print information about the coloring and the produced index sets
180: .   -snes_fd_color - instruct SNES to using coloring and then MatFDColoring to compute the Jacobians
181: -   -snes_fd_color_use_mat - instruct SNES to color the matrix directly instead of the DM from which the matrix comes (the default)

183:    Level: beginner

185: .seealso: MatColoring, MatColoringApply(), MatColoringSetDistance(), SNESComputeJacobianDefaultColor()
186: @*/
187: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
188: {
189:   PetscBool      flg;
190:   MatColoringType deft = MATCOLORINGSL;
191:   char           type[256];
193:   PetscInt       dist,maxcolors;

197:   MatColoringGetDistance(mc,&dist);
198:   if (dist == 2) deft = MATCOLORINGSL;
199:   else           deft = MATCOLORINGGREEDY;
200:   MatColoringGetMaxColors(mc,&maxcolors);
201:   MatColoringRegisterAll();
202:   PetscObjectOptionsBegin((PetscObject)mc);
203:   if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
204:   PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
205:   if (flg) {
206:     MatColoringSetType(mc,type);
207:   } else if (!((PetscObject)mc)->type_name) {
208:     MatColoringSetType(mc,deft);
209:   }
210:   PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
211:   if (flg) {MatColoringSetDistance(mc,dist);}
212:   PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
213:   if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
214:   if (mc->ops->setfromoptions) {
215:     (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
216:   }
217:   PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
218:   PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,NULL);
219:   PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
220:   PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
221:   PetscOptionsEnd();
222:   return(0);
223: }

225: /*@
226:    MatColoringSetDistance - Sets the distance of the coloring

228:    Logically Collective on MatColoring

230:    Input Parameters:
231: +  mc - the MatColoring context
232: -  dist - the distance the coloring should compute

234:    Level: beginner

236:    Notes:
237:     The distance of the coloring denotes the minimum number
238:    of edges in the graph induced by the matrix any two vertices
239:    of the same color are.  Distance-1 colorings are the classical
240:    coloring, where no two vertices of the same color are adjacent.
241:    distance-2 colorings are useful for the computation of Jacobians.

243: .seealso: MatColoringGetDistance(), MatColoringApply()
244: @*/
245: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
246: {
249:   mc->dist = dist;
250:   return(0);
251: }

253: /*@
254:    MatColoringGetDistance - Gets the distance of the coloring

256:    Logically Collective on MatColoring

258:    Input Parameter:
259: .  mc - the MatColoring context

261:    Output Parameter:
262: .  dist - the current distance being used for the coloring.

264:    Level: beginner

266: .seealso: MatColoringSetDistance(), MatColoringApply()
267: @*/
268: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
269: {
272:   if (dist) *dist = mc->dist;
273:   return(0);
274: }

276: /*@
277:    MatColoringSetMaxColors - Sets the maximum number of colors

279:    Logically Collective on MatColoring

281:    Input Parameter:
282: +  mc - the MatColoring context
283: -  maxcolors - the maximum number of colors to produce

285:    Level: beginner

287:    Notes:
288:     This may be used to compute a certain number of
289:    independent sets from the graph.  For instance, while using
290:    MATCOLORINGMIS and maxcolors = 1, one gets out an MIS.  Vertices
291:    not in a color are set to have color maxcolors+1, which is not
292:    a valid color as they may be adjacent.

294: .seealso: MatColoringGetMaxColors(), MatColoringApply()
295: @*/
296: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
297: {
300:   mc->maxcolors = maxcolors;
301:   return(0);
302: }

304: /*@
305:    MatColoringGetMaxColors - Gets the maximum number of colors

307:    Logically Collective on MatColoring

309:    Input Parameter:
310: .  mc - the MatColoring context

312:    Output Parameter:
313: .  maxcolors - the current maximum number of colors to produce

315:    Level: beginner

317: .seealso: MatColoringSetMaxColors(), MatColoringApply()
318: @*/
319: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
320: {
323:   if (maxcolors) *maxcolors = mc->maxcolors;
324:   return(0);
325: }

327: /*@
328:    MatColoringApply - Apply the coloring to the matrix, producing index
329:    sets corresponding to a number of independent sets in the induced
330:    graph.

332:    Collective on MatColoring

334:    Input Parameters:
335: .  mc - the MatColoring context

337:    Output Parameter:
338: .  coloring - the ISColoring instance containing the coloring

340:    Level: beginner

342: .seealso: MatColoring, MatColoringCreate()
343: @*/
344: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
345: {
346:   PetscErrorCode    ierr;
347:   PetscBool         flg;
348:   PetscViewerFormat format;
349:   PetscViewer       viewer;
350:   PetscInt          nc,ncolors;

354:   PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
355:   (*mc->ops->apply)(mc,coloring);
356:   PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);

358:   /* valid */
359:   if (mc->valid) {
360:     MatColoringTest(mc,*coloring);
361:   }
362:   if (mc->valid_iscoloring) {
363:     MatISColoringTest(mc->mat,*coloring);
364:   }

366:   /* view */
367:   PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
368:   if (flg && !PetscPreLoadingOn) {
369:     PetscViewerPushFormat(viewer,format);
370:     MatColoringView(mc,viewer);
371:     MatGetSize(mc->mat,NULL,&nc);
372:     ISColoringGetIS(*coloring,PETSC_USE_POINTER,&ncolors,NULL);
373:     PetscViewerASCIIPrintf(viewer,"  Number of colors %d\n",ncolors);
374:     PetscViewerASCIIPrintf(viewer,"  Number of total columns %d\n",nc);
375:     if (nc <= 1000) {ISColoringView(*coloring,viewer);}
376:     PetscViewerPopFormat(viewer);
377:     PetscViewerDestroy(&viewer);
378:   }
379:   return(0);
380: }

382: /*@
383:    MatColoringView - Output details about the MatColoring.

385:    Collective on MatColoring

387:    Input Parameters:
388: -  mc - the MatColoring context
389: +  viewer - the Viewer context

391:    Level: beginner

393: .seealso: MatColoring, MatColoringApply()
394: @*/
395: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
396: {
398:   PetscBool      iascii;

402:   if (!viewer) {
403:     PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
404:   }

408:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
409:   if (iascii) {
410:     PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
411:     PetscViewerASCIIPrintf(viewer,"  Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
412:     if (mc->maxcolors > 0) {
413:       PetscViewerASCIIPrintf(viewer,"  Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
414:     } else {
415:       PetscViewerASCIIPrintf(viewer,"  Distance %d\n",mc->dist);
416:     }
417:   }
418:   return(0);
419: }

421: /*@
422:    MatColoringSetWeightType - Set the type of weight computation used.

424:    Logically collective on MatColoring

426:    Input Parameters:
427: -  mc - the MatColoring context
428: +  wt - the weight type

430:    Level: beginner

432: .seealso: MatColoring, MatColoringWeightType
433: @*/
434: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
435: {
437:   mc->weight_type = wt;
438:   return(0);

440: }