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, No Fortran Support

     12:   Input Parameters:
     13: + sname    - name of Coloring (for example `MATCOLORINGSL`)
     14: - function - function pointer that creates the coloring

     16:   Level: developer

     18:   Example Usage:
     19: .vb
     20:    MatColoringRegister("my_color", MyColor);
     21: .ve

     23:   Then, your partitioner can be chosen with the procedural interface via `MatColoringSetType(part, "my_color")`  or at runtime via the option
     24:   `-mat_coloring_type my_color`

     26: .seealso: `MatColoringType`, `MatColoringRegisterDestroy()`, `MatColoringRegisterAll()`
     27: @*/
     28: PetscErrorCode MatColoringRegister(const char sname[], PetscErrorCode (*function)(MatColoring))
     29: {
     30:   PetscFunctionBegin;
     31:   PetscCall(MatInitializePackage());
     32:   PetscCall(PetscFunctionListAdd(&MatColoringList, sname, function));
     33:   PetscFunctionReturn(PETSC_SUCCESS);
     34: }

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

     39:   Collective

     41:   Input Parameter:
     42: . m - a `Mat` from which a coloring is derived

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

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

     55:   Level: beginner

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

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

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

     65:   Some coloring types only support distance two colorings

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

     73:   PetscFunctionBegin;
     75:   PetscAssertPointer(mcptr, 2);
     76:   PetscCall(MatInitializePackage());

     78:   PetscCall(PetscHeaderCreate(mc, MAT_COLORING_CLASSID, "MatColoring", "Matrix coloring", "MatColoring", PetscObjectComm((PetscObject)m), MatColoringDestroy, MatColoringView));
     79:   PetscCall(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:   PetscFunctionReturn(PETSC_SUCCESS);
     89: }

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

     94:   Collective

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

     99:   Level: beginner

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

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

    121:   Collective

    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);

    144:   PetscFunctionBegin;
    146:   PetscAssertPointer(type, 2);
    147:   PetscCall(PetscObjectTypeCompare((PetscObject)mc, type, &match));
    148:   if (match) PetscFunctionReturn(PETSC_SUCCESS);
    149:   PetscCall(PetscFunctionListFind(MatColoringList, type, &r));
    150:   PetscCheck(r, PetscObjectComm((PetscObject)mc), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unable to find requested MatColoring type %s", type);

    152:   PetscTryTypeMethod(mc, destroy);
    153:   mc->ops->destroy        = NULL;
    154:   mc->ops->apply          = NULL;
    155:   mc->ops->view           = NULL;
    156:   mc->ops->setfromoptions = NULL;
    157:   mc->ops->destroy        = NULL;

    159:   PetscCall(PetscObjectChangeTypeName((PetscObject)mc, type));
    160:   PetscCall((*r)(mc));
    161:   PetscFunctionReturn(PETSC_SUCCESS);
    162: }

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

    167:   Collective

    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 = MATCOLORINGGREEDY;
    188:   char            type[256];
    189:   PetscInt        dist, maxcolors;

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

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

    221:   Logically Collective

    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: {
    243:   PetscFunctionBegin;
    245:   mc->dist = dist;
    246:   PetscFunctionReturn(PETSC_SUCCESS);
    247: }

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

    252:   Logically Collective

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

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

    260:   Level: beginner

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

    269: .seealso: `MatColoring`, `MatColoringSetDistance()`, `MatColoringApply()`
    270: @*/
    271: PetscErrorCode MatColoringGetDistance(MatColoring mc, PetscInt *dist)
    272: {
    273:   PetscFunctionBegin;
    275:   if (dist) *dist = mc->dist;
    276:   PetscFunctionReturn(PETSC_SUCCESS);
    277: }

    279: /*@
    280:   MatColoringSetMaxColors - Sets the maximum number of colors to produce

    282:   Logically Collective

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

    288:   Level: beginner

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

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

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

    300: .seealso: `MatColoring`, `MatColoringGetMaxColors()`, `MatColoringApply()`
    301: @*/
    302: PetscErrorCode MatColoringSetMaxColors(MatColoring mc, PetscInt maxcolors)
    303: {
    304:   PetscFunctionBegin;
    306:   mc->maxcolors = maxcolors;
    307:   PetscFunctionReturn(PETSC_SUCCESS);
    308: }

    310: /*@
    311:   MatColoringGetMaxColors - Gets the maximum number of colors

    313:   Logically Collective

    315:   Input Parameter:
    316: . mc - the `MatColoring` context

    318:   Output Parameter:
    319: . maxcolors - the current maximum number of colors to produce

    321:   Level: beginner

    323: .seealso: `MatColoring`, `MatColoringSetMaxColors()`, `MatColoringApply()`
    324: @*/
    325: PetscErrorCode MatColoringGetMaxColors(MatColoring mc, PetscInt *maxcolors)
    326: {
    327:   PetscFunctionBegin;
    329:   if (maxcolors) *maxcolors = mc->maxcolors;
    330:   PetscFunctionReturn(PETSC_SUCCESS);
    331: }

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

    338:   Collective

    340:   Input Parameter:
    341: . mc - the `MatColoring` context

    343:   Output Parameter:
    344: . coloring - the `ISColoring` instance containing the coloring

    346:   Level: beginner

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

    357:   PetscFunctionBegin;
    359:   PetscAssertPointer(coloring, 2);
    360:   PetscCall(PetscLogEventBegin(MATCOLORING_Apply, mc, 0, 0, 0));
    361:   PetscUseTypeMethod(mc, apply, coloring);
    362:   PetscCall(PetscLogEventEnd(MATCOLORING_Apply, mc, 0, 0, 0));

    364:   /* valid */
    365:   if (mc->valid) PetscCall(MatColoringTest(mc, *coloring));
    366:   if (mc->valid_iscoloring) PetscCall(MatISColoringTest(mc->mat, *coloring));

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

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

    387:   Collective

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

    393:   Level: beginner

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

    401:   PetscFunctionBegin;
    403:   if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc), &viewer));
    405:   PetscCheckSameComm(mc, 1, viewer, 2);

    407:   PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
    408:   if (isascii) {
    409:     PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)mc, viewer));
    410:     PetscCall(PetscViewerASCIIPrintf(viewer, "  Weight type: %s\n", MatColoringWeightTypes[mc->weight_type]));
    411:     if (mc->maxcolors > 0) {
    412:       PetscCall(PetscViewerASCIIPrintf(viewer, "  Distance %" PetscInt_FMT ", Max. Colors %" PetscInt_FMT "\n", mc->dist, mc->maxcolors));
    413:     } else {
    414:       PetscCall(PetscViewerASCIIPrintf(viewer, "  Distance %" PetscInt_FMT "\n", mc->dist));
    415:     }
    416:   }
    417:   PetscFunctionReturn(PETSC_SUCCESS);
    418: }

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

    423:   Logically Collective

    425:   Input Parameters:
    426: + mc - the `MatColoring` context
    427: - wt - the weight type

    429:   Level: beginner

    431: .seealso: `MatColoring`, `MatColoringWeightType`, `MatColoringApply()`
    432: @*/
    433: PetscErrorCode MatColoringSetWeightType(MatColoring mc, MatColoringWeightType wt)
    434: {
    435:   PetscFunctionBegin;
    436:   mc->weight_type = wt;
    437:   PetscFunctionReturn(PETSC_SUCCESS);
    438: }