Actual source code: matcoloring.c

petsc-master 2020-11-29
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: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
 83:   MatInitializePackage();
 84: #endif
 85:   PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
 86:   PetscObjectReference((PetscObject)m);
 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:   return(0);
 96: }


 99: /*@
100:    MatColoringDestroy - Destroys the matrix coloring context

102:    Collective on MatColoring

104:    Input Parameter:
105: .  mc - the MatColoring context

107:    Level: beginner

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

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

125: /*@C
126:    MatColoringSetType - Sets the type of coloring algorithm used

128:    Collective on MatColoring

130:    Input Parameter:
131: +  mc - the MatColoring context
132: -  type - the type of coloring

134:    Level: beginner

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.

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

151:   PetscObjectTypeCompare((PetscObject)mc,type,&match);
152:   if (match) return(0);
153:    PetscFunctionListFind(MatColoringList,type,&r);
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:     (*(mc)->ops->destroy)(mc);
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;

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

169: /*@
170:    MatColoringSetFromOptions - Sets MatColoring options from user parameters

172:    Collective on MatColoring

174:    Input Parameters:
175: .  mc - MatColoring context

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)

185:    Level: beginner

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

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

227: /*@
228:    MatColoringSetDistance - Sets the distance of the coloring

230:    Logically Collective on MatColoring

232:    Input Parameters:
233: +  mc - the MatColoring context
234: -  dist - the distance the coloring should compute

236:    Level: beginner

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.

245: .seealso: MatColoringGetDistance(), MatColoringApply()
246: @*/
247: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
248: {
251:   mc->dist = dist;
252:   return(0);
253: }

255: /*@
256:    MatColoringGetDistance - Gets the distance of the coloring

258:    Logically Collective on MatColoring

260:    Input Parameter:
261: .  mc - the MatColoring context

263:    Output Parameter:
264: .  dist - the current distance being used for the coloring.

266:    Level: beginner

268: .seealso: MatColoringSetDistance(), MatColoringApply()
269: @*/
270: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
271: {
274:   if (dist) *dist = mc->dist;
275:   return(0);
276: }

278: /*@
279:    MatColoringSetMaxColors - Sets the maximum number of colors

281:    Logically Collective on MatColoring

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

287:    Level: beginner

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.

296: .seealso: MatColoringGetMaxColors(), MatColoringApply()
297: @*/
298: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
299: {
302:   mc->maxcolors = maxcolors;
303:   return(0);
304: }

306: /*@
307:    MatColoringGetMaxColors - Gets the maximum number of colors

309:    Logically Collective on MatColoring

311:    Input Parameter:
312: .  mc - the MatColoring context

314:    Output Parameter:
315: .  maxcolors - the current maximum number of colors to produce

317:    Level: beginner

319: .seealso: MatColoringSetMaxColors(), MatColoringApply()
320: @*/
321: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
322: {
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 on MatColoring

336:    Input Parameters:
337: .  mc - the MatColoring context

339:    Output Parameter:
340: .  coloring - the ISColoring instance containing the coloring

342:    Level: beginner

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

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

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

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

384: /*@
385:    MatColoringView - Output details about the MatColoring.

387:    Collective on MatColoring

389:    Input Parameters:
390: -  mc - the MatColoring context
391: +  viewer - the Viewer context

393:    Level: beginner

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

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

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

423: /*@
424:    MatColoringSetWeightType - Set the type of weight computation used.

426:    Logically collective on MatColoring

428:    Input Parameters:
429: -  mc - the MatColoring context
430: +  wt - the weight type

432:    Level: beginner

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

442: }