Actual source code: matcoloring.c

  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: `MatColoringType`, `MatColoringRegisterDestroy()`, `MatColoringRegisterAll()`
 29: @*/
 30: PetscErrorCode MatColoringRegister(const char sname[], PetscErrorCode (*function)(MatColoring))
 31: {
 32:   MatInitializePackage();
 33:   PetscFunctionListAdd(&MatColoringList, sname, function);
 34:   return 0;
 35: }

 37: /*@
 38:    MatColoringCreate - Creates a matrix coloring context.

 40:    Collective on m

 42:    Input Parameters:
 43: .  comm - MPI communicator

 45:    Output Parameter:
 46: .  mcptr - the new `MatColoring` context

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

 56:    Level: beginner

 58:    Notes:
 59:    A distance one coloring is useful, for example, multi-color SOR.

 61:    A distance two coloring is for the finite difference computation of Jacobians (see `MatFDColoringCreate())`.

 63:    Coloring of matrices can be computed directly from the sparse matrix nonzero structure via the `MatColoring` object or from the mesh from which the
 64:    matrix comes from with `DMCreateColoring()`. In general using the mesh produces a more optimal coloring (fewer colors).

 66:           Some coloring types only support distance two colorings

 68: .seealso: `MatColoringSetFromOptions()`, `MatColoring`, `MatColoringApply()`, `MatFDColoringCreate()`, `DMCreateColoring()`, `MatColoringType`
 69: @*/
 70: PetscErrorCode MatColoringCreate(Mat m, MatColoring *mcptr)
 71: {
 72:   MatColoring mc;

 76:   *mcptr = NULL;

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

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

 95:    Collective on mc

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

100:    Level: beginner

102: .seealso: `MatColoring`, `MatColoringCreate()`, `MatColoringApply()`
103: @*/
104: PetscErrorCode MatColoringDestroy(MatColoring *mc)
105: {
106:   if (--((PetscObject)(*mc))->refct > 0) {
107:     *mc = NULL;
108:     return 0;
109:   }
110:   MatDestroy(&(*mc)->mat);
111:   if ((*mc)->ops->destroy) (*((*mc)->ops->destroy))(*mc);
112:   if ((*mc)->user_weights) PetscFree((*mc)->user_weights);
113:   if ((*mc)->user_lperm) PetscFree((*mc)->user_lperm);
114:   PetscHeaderDestroy(mc);
115:   return 0;
116: }

118: /*@C
119:    MatColoringSetType - Sets the type of coloring algorithm used

121:    Collective on type

123:    Input Parameters:
124: +  mc - the `MatColoring` context
125: -  type - the type of coloring

127:    Options Database Key:
128: .  -mat_coloring_type type - the name of the type

130:    Level: beginner

132:    Note:
133:     Possible types include the sequential types `MATCOLORINGLF`,
134:    `MATCOLORINGSL`, and `MATCOLORINGID` from the MINPACK package as well
135:    as a parallel `MATCOLORINGGREEDY` algorithm.

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

146:   PetscObjectTypeCompare((PetscObject)mc, type, &match);
147:   if (match) return 0;
148:   PetscFunctionListFind(MatColoringList, type, &r);
150:   if (mc->ops->destroy) {
151:     (*(mc)->ops->destroy)(mc);
152:     mc->ops->destroy = NULL;
153:   }
154:   mc->ops->apply          = NULL;
155:   mc->ops->view           = NULL;
156:   mc->ops->setfromoptions = NULL;
157:   mc->ops->destroy        = NULL;

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

164: /*@
165:    MatColoringSetFromOptions - Sets `MatColoring` options from options database

167:    Collective on mc

169:    Input Parameter:
170: .  mc - `MatColoring` context

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

180:    Level: beginner

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

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

218: /*@
219:    MatColoringSetDistance - Sets the distance of the coloring

221:    Logically Collective on dist

223:    Input Parameters:
224: +  mc - the `MatColoring` context
225: -  dist - the distance the coloring should compute

227:    Options Database Key:
228: .   -mat_coloring_type - the type of coloring algorithm used. See `MatColoringType`.

230:    Level: beginner

232:    Note:
233:     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: .seealso: `MatColoring`, `MatColoringSetFromOptions()`, `MatColoringGetDistance()`, `MatColoringApply()`
240: @*/
241: PetscErrorCode MatColoringSetDistance(MatColoring mc, PetscInt dist)
242: {
244:   mc->dist = dist;
245:   return 0;
246: }

248: /*@
249:    MatColoringGetDistance - Gets the distance of the coloring

251:    Logically Collective on mc

253:    Input Parameter:
254: .  mc - the `MatColoring` context

256:    Output Parameter:
257: .  dist - the current distance being used for the coloring.

259:    Level: beginner

261:    Note:
262:     The distance of the coloring denotes the minimum number
263:    of edges in the graph induced by the matrix any two vertices
264:    of the same color are.  Distance-1 colorings are the classical
265:    coloring, where no two vertices of the same color are adjacent.
266:    distance-2 colorings are useful for the computation of Jacobians.

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

277: /*@
278:    MatColoringSetMaxColors - Sets the maximum number of colors to produce

280:    Logically Collective on mc

282:    Input Parameters:
283: +  mc - the `MatColoring` context
284: -  maxcolors - the maximum number of colors to produce

286:    Level: beginner

288:    Notes:
289:    Vertices not in an available color are set to have color maxcolors+1, which is not
290:    a valid color as they may be adjacent.

292:    This works only for  `MATCOLORINGGREEDY` and `MATCOLORINGJP`

294:    This may be used to compute a certain number of
295:    independent sets from the graph.  For instance, while using
296:    `MATCOLORINGGREEDY` and maxcolors = 1, one gets out an MIS.

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

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

310:    Logically Collective on mc

312:    Input Parameter:
313: .  mc - the `MatColoring` context

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

318:    Level: beginner

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

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

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

342:    Level: beginner

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

355:   PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0);
356:   PetscUseTypeMethod(mc, apply, coloring);
357:   PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0);

359:   /* valid */
360:   if (mc->valid) MatColoringTest(mc, *coloring);
361:   if (mc->valid_iscoloring) MatISColoringTest(mc->mat, *coloring);

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

379: /*@
380:    MatColoringView - Output details about the `MatColoring`.

382:    Collective on mc

384:    Input Parameters:
385: -  mc - the `MatColoring` context
386: +  viewer - the Viewer context

388:    Level: beginner

390: .seealso: `PetscViewer`, `MatColoring`, `MatColoringApply()`
391: @*/
392: PetscErrorCode MatColoringView(MatColoring mc, PetscViewer viewer)
393: {
394:   PetscBool iascii;

397:   if (!viewer) PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer);

401:   PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii);
402:   if (iascii) {
403:     PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer);
404:     PetscViewerASCIIPrintf(viewer, "  Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]);
405:     if (mc->maxcolors > 0) {
406:       PetscViewerASCIIPrintf(viewer, "  Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors);
407:     } else {
408:       PetscViewerASCIIPrintf(viewer, "  Distance %" PetscInt_FMT "\n", mc->dist);
409:     }
410:   }
411:   return 0;
412: }

414: /*@
415:    MatColoringSetWeightType - Set the type of weight computation used while computing the coloring

417:    Logically collective on MatColoring

419:    Input Parameters:
420: -  mc - the `MatColoring` context
421: +  wt - the weight type

423:    Level: beginner

425: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
426: @*/
427: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
428: {
429:   mc->weight_type = wt;
430:   return 0;
431: }