Actual source code: matcoloring.c

petsc-3.8.2 2017-11-09
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:   PetscFunctionListAdd(&MatColoringList,sname,function);
 38:   return(0);
 39: }

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

 44:    Collective on MatColoring

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

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

 52:    Options Database Keys:
 53: +   -mat_coloring_type - the type of coloring algorithm used
 54: .   -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
 55: .   -mat_coloring_distance - compute a distance 1,2,... coloring.
 56: .   -mat_coloring_view - print information about the coloring and the produced index sets
 57: -   -mat_coloring_valid - debugging option that prints all coloring incompatibilities

 59:    Level: beginner

 61: .keywords: Coloring, Matrix

 63: .seealso: MatColoring, MatColoringApply()
 64: @*/
 65: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
 66: {
 67:   MatColoring    mc;

 73:   *mcptr = NULL;

 75: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
 76:   MatInitializePackage();
 77: #endif
 78:   PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
 79:   PetscObjectReference((PetscObject)m);
 80:   mc->mat       = m;
 81:   mc->dist      = 2; /* default to Jacobian computation case */
 82:   mc->maxcolors = IS_COLORING_MAX;
 83:   *mcptr        = mc;
 84:   mc->valid     = PETSC_FALSE;
 85:   mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
 86:   mc->user_weights = NULL;
 87:   mc->user_lperm = NULL;
 88:   return(0);
 89: }


 92: /*@
 93:    MatColoringDestroy - Destroys the matrix coloring context

 95:    Collective on MatColoring

 97:    Input Parameter:
 98: .  mc - the MatColoring context

100:    Level: beginner

102: .keywords: Coloring, destroy

104: .seealso: MatColoringCreate(), MatColoringApply()
105: @*/
106: PetscErrorCode MatColoringDestroy(MatColoring *mc)
107: {

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

120: /*@C
121:    MatColoringSetType - Sets the type of coloring algorithm used

123:    Collective on MatColoring

125:    Input Parameter:
126: +  mc - the MatColoring context
127: -  type - the type of coloring

129:    Level: beginner

131:    Notes:  Possible types include the sequential types MATCOLORINGLF,
132:    MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
133:    as a parallel MATCOLORINGMIS algorithm.

135: .keywords: Coloring, type

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

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

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

165: /*@
166:    MatColoringSetFromOptions - Sets MatColoring options from user parameters

168:    Collective on MatColoring

170:    Input Parameters:
171: .  mc - MatColoring context

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

179:    Level: beginner

181: .keywords: Coloring, Matrix

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

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

222: /*@
223:    MatColoringSetDistance - Sets the distance of the coloring

225:    Logically Collective on MatColoring

227:    Input Parameter:
228: .  mc - the MatColoring context
229: .  dist - the distance the coloring should compute

231:    Level: beginner

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

239: .keywords: Coloring, distance, Jacobian

241: .seealso: MatColoringGetDistance(), MatColoringApply()
242: @*/
243: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
244: {
247:   mc->dist = dist;
248:   return(0);
249: }

251: /*@
252:    MatColoringGetDistance - Gets the distance of the coloring

254:    Logically Collective on MatColoring

256:    Input Parameter:
257: .  mc - the MatColoring context

259:    Output Paramter:
260: .  dist - the current distance being used for the coloring.

262:    Level: beginner

264: .keywords: Coloring, distance

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

293: .keywords: Coloring

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

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

308:    Logically Collective on MatColoring

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

313:    Output Paramter:
314: .  maxcolors - the current maximum number of colors to produce

316:    Level: beginner

318: .keywords: Coloring

320: .seealso: MatColoringSetMaxColors(), MatColoringApply()
321: @*/
322: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
323: {
326:   if (maxcolors) *maxcolors = mc->maxcolors;
327:   return(0);
328: }

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

335:    Collective on MatColoring

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

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

343:    Level: beginner

345: .keywords: Coloring, Apply

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

359:   PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
360:   (*mc->ops->apply)(mc,coloring);
361:   PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
362:   /* valid */
363:   if (mc->valid) {
364:     MatColoringTestValid(mc,*coloring);
365:   }
366:   /* view */
367:   PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((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,&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: .keywords: Coloring, view

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

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

444: }