Actual source code: matcoloring.c

petsc-3.5.3 2015-01-31
Report Typos and Errors
  1: #include <petsc-private/matimpl.h>      /*I "petscmat.h"  I*/

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

  7: PETSC_EXTERN PetscErrorCode MatColoringTestValid(MatColoring,ISColoring);

 11: /*@C
 12:    MatColoringRegister - Adds a new sparse matrix coloring to the  matrix package.

 14:    Not Collective

 16:    Input Parameters:
 17: +  sname - name of Coloring (for example MATCOLORINGSL)
 18: -  function - function pointer that creates the coloring

 20:    Level: developer

 22:    Sample usage:
 23: .vb
 24:    MatColoringRegister("my_color",MyColor);
 25: .ve

 27:    Then, your partitioner can be chosen with the procedural interface via
 28: $     MatColoringSetType(part,"my_color")
 29:    or at runtime via the option
 30: $     -mat_coloring_type my_color

 32: .keywords: matrix, Coloring, register

 34: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
 35: @*/
 36: PetscErrorCode  MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
 37: {

 41:   PetscFunctionListAdd(&MatColoringList,sname,function);
 42:   return(0);
 43: }

 47: /*@
 48:    MatColoringCreate - Creates a matrix coloring context.

 50:    Collective on MatColoring

 52:    Input Parameters:
 53: .  comm - MPI communicator

 55:    Output Parameter:
 56: .  mcptr - the new MatColoring context

 58:    Options Database Keys:
 59: +   -mat_coloring_type - the type of coloring algorithm used
 60: .   -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
 61: .   -mat_coloring_distance - compute a distance 1,2,... coloring.
 62: .   -mat_coloring_view - print information about the coloring and the produced index sets
 63: -   -mat_coloring_valid - debugging option that prints all coloring incompatibilities

 65:    Level: beginner

 67: .keywords: Coloring, Matrix

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

 77:   *mcptr = 0;

 79: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
 80:   MatInitializePackage();
 81: #endif
 82:   PetscHeaderCreate(mc,_p_MatColoring, struct _MatColoringOps, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring",
 83:                            "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: }


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

102:    Collective on MatColoring

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

107:    Level: beginner

109: .keywords: Coloring, destroy

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

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

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

132:    Collective on MatColoring

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

138:    Level: beginner

140:    Notes:  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: }

176: /*@
177:    MatColoringSetFromOptions - Sets MatColoring options from user parameters

179:    Collective on MatColoring

181:    Input Parameters:
182: .  mc - MatColoring context

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

190:    Level: beginner

192: .keywords: Coloring, Matrix

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

206:   MatColoringGetDistance(mc,&dist);
207:   MatColoringGetMaxColors(mc,&maxcolors);
208:   if (!MatColoringRegisterAllCalled) {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)(mc);
223:   }
224:   PetscOptionsBool("-mat_coloring_valid","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
225:   PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
226:   PetscObjectProcessOptionsHandlers((PetscObject)mc);
227:   PetscOptionsEnd();
228:   return(0);
229: }

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

236:    Logically Collective on MatColoring

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

242:    Level: beginner

244:    Notes: 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: }

264: /*@
265:    MatColoringGetDistance - Gets the distance of the coloring

267:    Logically Collective on MatColoring

269:    Input Parameter:
270: .  mc - the MatColoring context

272:    Output Paramter:
273: .  dist - the current distance being used for the coloring.

275:    Level: beginner

277: .keywords: Coloring, distance

279: .seealso: MatColoringSetDistance(), MatColoringApply()
280: @*/
281: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
282: {
285:   if (dist) *dist = mc->dist;
286:   return(0);
287: }

291: /*@
292:    MatColoringSetMaxColors - Sets the maximum number of colors

294:    Logically Collective on MatColoring

296:    Input Parameter:
297: +  mc - the MatColoring context
298: -  maxcolors - the maximum number of colors to produce

300:    Level: beginner

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

308: .keywords: Coloring

310: .seealso: MatColoringGetMaxColors(), MatColoringApply()
311: @*/
312: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
313: {
316:   mc->maxcolors = maxcolors;
317:   return(0);
318: }

322: /*@
323:    MatColoringGetMaxColors - Gets the maximum number of colors

325:    Logically Collective on MatColoring

327:    Input Parameter:
328: .  mc - the MatColoring context

330:    Output Paramter:
331: .  maxcolors - the current maximum number of colors to produce

333:    Level: beginner

335: .keywords: Coloring

337: .seealso: MatColoringSetMaxColors(), MatColoringApply()
338: @*/
339: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
340: {
343:   if (maxcolors) *maxcolors = mc->maxcolors;
344:   return(0);
345: }

349: /*@
350:    MatColoringApply - Apply the coloring to the matrix, producing index
351:    sets corresponding to a number of independent sets in the induced
352:    graph.

354:    Collective on MatColoring

356:    Input Parameters:
357: .  mc - the MatColoring context

359:    Output Parameter:
360: .  coloring - the ISColoring instance containing the coloring

362:    Level: beginner

364: .keywords: Coloring, Apply

366: .seealso: MatColoring, MatColoringCreate()
367: @*/
368: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
369: {
370:   PetscErrorCode    ierr;
371:   PetscBool         flg;
372:   PetscViewerFormat format;
373:   PetscViewer       viewer;
374:   PetscInt          nc,ncolors;

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

403: /*@
404:    MatColoringView - Output details about the MatColoring.

406:    Collective on MatColoring

408:    Input Parameters:
409: -  mc - the MatColoring context
410: +  viewer - the Viewer context

412:    Level: beginner

414: .keywords: Coloring, view

416: .seealso: MatColoring, MatColoringApply()
417: @*/
418: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
419: {
421:   PetscBool      iascii;

425:   if (!viewer) {
426:     PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
427:   }

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

444: /*@
445:    MatColoringSetWeightType - Set the type of weight computation used.

447:    Logically collective on MatColoring

449:    Input Parameters:
450: -  mc - the MatColoring context
451: +  wt - the weight type

453:    Level: beginner

455: .keywords: Coloring, view

457: .seealso: MatColoring, MatColoringWeightType
458: @*/
461: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
462: {
464:   mc->weight_type = wt;
465:   return(0);

467: }