Actual source code: matcoloring.c

petsc-3.11.1 2019-04-17
Report Typos and Errors
  1:  #include <petsc/private/matimpl.h>

  3: PetscFunctionList MatColoringList              = 0;
  4: PetscBool         MatColoringRegisterAllCalled = PETSC_FALSE;
  5: const char *const MatColoringWeightTypes[] = {"RANDOM","LEXICAL","LF","SL","MatColoringWeightType","MAT_COLORING_WEIGHT_",0};

  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: .keywords: matrix, Coloring, register

 30: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
 31: @*/
 32: PetscErrorCode  MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
 33: {

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

 42: /*@
 43:    MatColoringCreate - Creates a matrix coloring context.

 45:    Collective on MatColoring

 47:    Input Parameters:
 48: .  comm - MPI communicator

 50:    Output Parameter:
 51: .  mcptr - the new MatColoring context

 53:    Options Database Keys:
 54: +   -mat_coloring_type - the type of coloring algorithm used
 55: .   -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
 56: .   -mat_coloring_distance - compute a distance 1,2,... coloring.
 57: .   -mat_coloring_view - print information about the coloring and the produced index sets
 58: .   -mat_coloring_test - debugging option that prints all coloring incompatibilities
 59: -   -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring

 61:    Level: beginner

 63:    Notes:
 64:     A distance one coloring is useful, for example, multi-color SOR. A distance two coloring is for the finite difference computation of Jacobians 
 65:           (see MatFDColoringCreate()).

 67:           Some coloring types only support distance two colorings

 69: .keywords: Coloring, Matrix

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

 81:   *mcptr = NULL;

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


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

103:    Collective on MatColoring

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

108:    Level: beginner

110: .keywords: Coloring, destroy

112: .seealso: MatColoringCreate(), MatColoringApply()
113: @*/
114: PetscErrorCode MatColoringDestroy(MatColoring *mc)
115: {

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

128: /*@C
129:    MatColoringSetType - Sets the type of coloring algorithm used

131:    Collective on MatColoring

133:    Input Parameter:
134: +  mc - the MatColoring context
135: -  type - the type of coloring

137:    Level: beginner

139:    Notes:
140:     Possible types include the sequential types MATCOLORINGLF,
141:    MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
142:    as a parallel MATCOLORINGMIS algorithm.

144: .keywords: Coloring, type

146: .seealso: MatColoringCreate(), MatColoringApply()
147: @*/
148: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
149: {
150:   PetscBool      match;
151:   PetscErrorCode ierr,(*r)(MatColoring);

156:   PetscObjectTypeCompare((PetscObject)mc,type,&match);
157:   if (match) return(0);
158:    PetscFunctionListFind(MatColoringList,type,&r);
159:   if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
160:   if (mc->ops->destroy) {
161:     (*(mc)->ops->destroy)(mc);
162:     mc->ops->destroy = NULL;
163:   }
164:   mc->ops->apply            = 0;
165:   mc->ops->view             = 0;
166:   mc->ops->setfromoptions   = 0;
167:   mc->ops->destroy          = 0;

169:   PetscObjectChangeTypeName((PetscObject)mc,type);
170:   (*r)(mc);
171:   return(0);
172: }

174: /*@
175:    MatColoringSetFromOptions - Sets MatColoring options from user parameters

177:    Collective on MatColoring

179:    Input Parameters:
180: .  mc - MatColoring context

182:    Options Database Keys:
183: +   -mat_coloring_type - the type of coloring algorithm used
184: .   -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
185: .   -mat_coloring_distance - compute a distance 1,2,... coloring.
186: .   -mat_coloring_view - print information about the coloring and the produced index sets

188:    Level: beginner

190: .keywords: Coloring, Matrix

192: .seealso: MatColoring, MatColoringApply()
193: @*/
194: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
195: {
196:   PetscBool      flg;
197:   MatColoringType deft = MATCOLORINGSL;
198:   char           type[256];
200:   PetscInt       dist,maxcolors;

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

232: /*@
233:    MatColoringSetDistance - Sets the distance of the coloring

235:    Logically Collective on MatColoring

237:    Input Parameter:
238: .  mc - the MatColoring context
239: .  dist - the distance the coloring should compute

241:    Level: beginner

243:    Notes:
244:     The distance of the coloring denotes the minimum number
245:    of edges in the graph induced by the matrix any two vertices
246:    of the same color are.  Distance-1 colorings are the classical
247:    coloring, where no two vertices of the same color are adjacent.
248:    distance-2 colorings are useful for the computation of Jacobians.

250: .keywords: Coloring, distance, Jacobian

252: .seealso: MatColoringGetDistance(), MatColoringApply()
253: @*/
254: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
255: {
258:   mc->dist = dist;
259:   return(0);
260: }

262: /*@
263:    MatColoringGetDistance - Gets the distance of the coloring

265:    Logically Collective on MatColoring

267:    Input Parameter:
268: .  mc - the MatColoring context

270:    Output Paramter:
271: .  dist - the current distance being used for the coloring.

273:    Level: beginner

275: .keywords: Coloring, distance

277: .seealso: MatColoringSetDistance(), MatColoringApply()
278: @*/
279: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
280: {
283:   if (dist) *dist = mc->dist;
284:   return(0);
285: }

287: /*@
288:    MatColoringSetMaxColors - Sets the maximum number of colors

290:    Logically Collective on MatColoring

292:    Input Parameter:
293: +  mc - the MatColoring context
294: -  maxcolors - the maximum number of colors to produce

296:    Level: beginner

298:    Notes:
299:     This may be used to compute a certain number of
300:    independent sets from the graph.  For instance, while using
301:    MATCOLORINGMIS and maxcolors = 1, one gets out an MIS.  Vertices
302:    not in a color are set to have color maxcolors+1, which is not
303:    a valid color as they may be adjacent.

305: .keywords: Coloring

307: .seealso: MatColoringGetMaxColors(), MatColoringApply()
308: @*/
309: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
310: {
313:   mc->maxcolors = maxcolors;
314:   return(0);
315: }

317: /*@
318:    MatColoringGetMaxColors - Gets the maximum number of colors

320:    Logically Collective on MatColoring

322:    Input Parameter:
323: .  mc - the MatColoring context

325:    Output Paramter:
326: .  maxcolors - the current maximum number of colors to produce

328:    Level: beginner

330: .keywords: Coloring

332: .seealso: MatColoringSetMaxColors(), MatColoringApply()
333: @*/
334: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
335: {
338:   if (maxcolors) *maxcolors = mc->maxcolors;
339:   return(0);
340: }

342: /*@
343:    MatColoringApply - Apply the coloring to the matrix, producing index
344:    sets corresponding to a number of independent sets in the induced
345:    graph.

347:    Collective on MatColoring

349:    Input Parameters:
350: .  mc - the MatColoring context

352:    Output Parameter:
353: .  coloring - the ISColoring instance containing the coloring

355:    Level: beginner

357: .keywords: Coloring, Apply

359: .seealso: MatColoring, MatColoringCreate()
360: @*/
361: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
362: {
363:   PetscErrorCode    ierr;
364:   PetscBool         flg;
365:   PetscViewerFormat format;
366:   PetscViewer       viewer;
367:   PetscInt          nc,ncolors;

371:   PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
372:   (*mc->ops->apply)(mc,coloring);
373:   PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);

375:   /* valid */
376:   if (mc->valid) {
377:     MatColoringTest(mc,*coloring);
378:   }
379:   if (mc->valid_iscoloring) {
380:     MatISColoringTest(mc->mat,*coloring);
381:   }

383:   /* view */
384:   PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->options,((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
385:   if (flg && !PetscPreLoadingOn) {
386:     PetscViewerPushFormat(viewer,format);
387:     MatColoringView(mc,viewer);
388:     MatGetSize(mc->mat,NULL,&nc);
389:     ISColoringGetIS(*coloring,&ncolors,NULL);
390:     PetscViewerASCIIPrintf(viewer,"  Number of colors %d\n",ncolors);
391:     PetscViewerASCIIPrintf(viewer,"  Number of total columns %d\n",nc);
392:     if (nc <= 1000) {ISColoringView(*coloring,viewer);}
393:     PetscViewerPopFormat(viewer);
394:     PetscViewerDestroy(&viewer);
395:   }
396:   return(0);
397: }

399: /*@
400:    MatColoringView - Output details about the MatColoring.

402:    Collective on MatColoring

404:    Input Parameters:
405: -  mc - the MatColoring context
406: +  viewer - the Viewer context

408:    Level: beginner

410: .keywords: Coloring, view

412: .seealso: MatColoring, MatColoringApply()
413: @*/
414: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
415: {
417:   PetscBool      iascii;

421:   if (!viewer) {
422:     PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
423:   }

427:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
428:   if (iascii) {
429:     PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
430:     PetscViewerASCIIPrintf(viewer,"  Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
431:     if (mc->maxcolors > 0) {
432:       PetscViewerASCIIPrintf(viewer,"  Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
433:     } else {
434:       PetscViewerASCIIPrintf(viewer,"  Distance %d\n",mc->dist);
435:     }
436:   }
437:   return(0);
438: }

440: /*@
441:    MatColoringSetWeightType - Set the type of weight computation used.

443:    Logically collective on MatColoring

445:    Input Parameters:
446: -  mc - the MatColoring context
447: +  wt - the weight type

449:    Level: beginner

451: .keywords: Coloring, view

453: .seealso: MatColoring, MatColoringWeightType
454: @*/
455: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
456: {
458:   mc->weight_type = wt;
459:   return(0);

461: }