1: #include <petsc/private/matimpl.h>

  3: /* Logging support */
  4: PetscClassId MAT_COARSEN_CLASSID;

  6: PetscFunctionList MatCoarsenList              = NULL;
  7: PetscBool         MatCoarsenRegisterAllCalled = PETSC_FALSE;

  9: /*@
 10:   MatCoarsenRegister - Adds a new sparse matrix coarsening algorithm to the matrix package.

 12:   Logically Collective, No Fortran Support

 14:   Input Parameters:
 15: + sname    - name of coarsen (for example `MATCOARSENMIS`)
 16: - function - function pointer that creates the coarsen type

 18:   Level: developer

 20:   Example Usage:
 21: .vb
 22:    MatCoarsenRegister("my_agg", MyAggCreate);
 23: .ve

 25:   Then, your aggregator can be chosen with the procedural interface via `MatCoarsenSetType(agg, "my_agg")` or at runtime via the option `-mat_coarsen_type my_agg`

 27: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenSetType()`, `MatCoarsenCreate()`, `MatCoarsenRegisterDestroy()`, `MatCoarsenRegisterAll()`
 28: @*/
 29: PetscErrorCode MatCoarsenRegister(const char sname[], PetscErrorCode (*function)(MatCoarsen))
 30: {
 31:   PetscFunctionBegin;
 32:   PetscCall(MatInitializePackage());
 33:   PetscCall(PetscFunctionListAdd(&MatCoarsenList, sname, function));
 34:   PetscFunctionReturn(PETSC_SUCCESS);
 35: }

 37: /*@
 38:   MatCoarsenGetType - Gets the Coarsen method type and name (as a string)
 39:   from the coarsen context.

 41:   Not Collective

 43:   Input Parameter:
 44: . coarsen - the coarsen context

 46:   Output Parameter:
 47: . type - coarsener type

 49:   Level: advanced

 51: .seealso: `MatCoarsen`, `MatCoarsenCreate()`, `MatCoarsenType`, `MatCoarsenSetType()`, `MatCoarsenRegister()`
 52: @*/
 53: PetscErrorCode MatCoarsenGetType(MatCoarsen coarsen, MatCoarsenType *type)
 54: {
 55:   PetscFunctionBegin;
 57:   PetscAssertPointer(type, 2);
 58:   *type = ((PetscObject)coarsen)->type_name;
 59:   PetscFunctionReturn(PETSC_SUCCESS);
 60: }

 62: /*@
 63:   MatCoarsenApply - Gets a coarsen for a matrix.

 65:   Collective

 67:   Input Parameter:
 68: . coarser - the coarsen

 70:   Options Database Keys:
 71: + -mat_coarsen_type (mis|hem|misk) - `mis`: maximal independent set based; `misk`: distance k MIS; `hem`: heavy edge matching
 72: - -mat_coarsen_view                - view the coarsening object

 74:   Level: advanced

 76:   Notes:
 77:   When the coarsening is used inside `PCGAMG` then the options database keys are prefixed with `-pc_gamg_`

 79:   Use `MatCoarsenGetData()` to access the results of the coarsening

 81:   The user can define additional coarsens; see `MatCoarsenRegister()`.

 83: .seealso: `MatCoarsen`, `MatCoarsenSetFromOptions()`, `MatCoarsenSetType()`, `MatCoarsenRegister()`, `MatCoarsenCreate()`,
 84:           `MatCoarsenDestroy()`, `MatCoarsenSetAdjacency()`,
 85:           `MatCoarsenGetData()`
 86: @*/
 87: PetscErrorCode MatCoarsenApply(MatCoarsen coarser)
 88: {
 89:   PetscFunctionBegin;
 91:   PetscAssertPointer(coarser, 1);
 92:   PetscCheck(coarser->graph->assembled, PetscObjectComm((PetscObject)coarser), PETSC_ERR_ARG_WRONGSTATE, "Not for unassembled matrix");
 93:   PetscCheck(!coarser->graph->factortype, PetscObjectComm((PetscObject)coarser), PETSC_ERR_ARG_WRONGSTATE, "Not for factored matrix");
 94:   PetscCall(PetscLogEventBegin(MAT_Coarsen, coarser, 0, 0, 0));
 95:   PetscUseTypeMethod(coarser, apply);
 96:   PetscCall(PetscLogEventEnd(MAT_Coarsen, coarser, 0, 0, 0));
 97:   PetscFunctionReturn(PETSC_SUCCESS);
 98: }

100: /*@
101:   MatCoarsenSetAdjacency - Sets the adjacency graph (matrix) of the thing to be coarsened.

103:   Collective

105:   Input Parameters:
106: + agg - the coarsen context
107: - adj - the adjacency matrix

109:   Level: advanced

111: .seealso: `MatCoarsen`, `MatCoarsenSetFromOptions()`, `Mat`, `MatCoarsenCreate()`, `MatCoarsenApply()`
112: @*/
113: PetscErrorCode MatCoarsenSetAdjacency(MatCoarsen agg, Mat adj)
114: {
115:   PetscFunctionBegin;
118:   agg->graph = adj;
119:   PetscFunctionReturn(PETSC_SUCCESS);
120: }

122: /*@
123:   MatCoarsenSetStrictAggs - Set whether to keep strict (non overlapping) aggregates in the linked list of aggregates for a coarsen context

125:   Logically Collective

127:   Input Parameters:
128: + agg - the coarsen context
129: - str - `PETSC_TRUE` keep strict aggregates, `PETSC_FALSE` allow overlap

131:   Level: advanced

133: .seealso: `MatCoarsen`, `MatCoarsenCreate()`, `MatCoarsenSetFromOptions()`
134: @*/
135: PetscErrorCode MatCoarsenSetStrictAggs(MatCoarsen agg, PetscBool str)
136: {
137:   PetscFunctionBegin;
139:   agg->strict_aggs = str;
140:   PetscFunctionReturn(PETSC_SUCCESS);
141: }

143: /*@
144:   MatCoarsenDestroy - Destroys the coarsen context.

146:   Collective

148:   Input Parameter:
149: . agg - the coarsen context

151:   Level: advanced

153: .seealso: `MatCoarsen`, `MatCoarsenCreate()`
154: @*/
155: PetscErrorCode MatCoarsenDestroy(MatCoarsen *agg)
156: {
157:   PetscFunctionBegin;
158:   if (!*agg) PetscFunctionReturn(PETSC_SUCCESS);
160:   if (--((PetscObject)*agg)->refct > 0) {
161:     *agg = NULL;
162:     PetscFunctionReturn(PETSC_SUCCESS);
163:   }

165:   PetscTryTypeMethod(*agg, destroy);
166:   if ((*agg)->agg_lists) PetscCall(PetscCDDestroy((*agg)->agg_lists));
167:   PetscCall(PetscObjectComposeFunction((PetscObject)*agg, "MatCoarsenSetMaximumIterations_C", NULL));
168:   PetscCall(PetscObjectComposeFunction((PetscObject)*agg, "MatCoarsenSetThreshold_C", NULL));
169:   PetscCall(PetscObjectComposeFunction((PetscObject)*agg, "MatCoarsenSetStrengthIndex_C", NULL));

171:   PetscCall(PetscHeaderDestroy(agg));
172:   PetscFunctionReturn(PETSC_SUCCESS);
173: }

175: /*@
176:   MatCoarsenViewFromOptions - View the coarsener from the options database

178:   Collective

180:   Input Parameters:
181: + A    - the coarsen context
182: . obj  - optional object that provides the prefix for the option name, pass `NULL` to use the options prefix of `A`
183: - name - command line option (usually `-mat_coarsen_view`)

185:   Options Database Key:
186: . -name viewer_specification - See `PetscOptionsCreateViewer()` for the values of `viewer_specification`

188:   Level: intermediate

190:   Note:
191:   This checks the options database, creates the viewer on-the-fly, uses it and then destroys it. Hence it should not be called in heavily used routines,
192:   rather `PetscOptionsCreateViewer()` should be used to construct the viewer once which can then be utilized in the heavily used routine.

194: .seealso: `MatCoarsen`, `MatCoarsenView()`, `PetscObjectViewFromOptions()`, `MatCoarsenCreate()`, `PetscOptionsCreateViewer()`
195: @*/
196: PetscErrorCode MatCoarsenViewFromOptions(MatCoarsen A, PetscObject obj, const char name[])
197: {
198:   PetscFunctionBegin;
200:   PetscCall(PetscObjectViewFromOptions((PetscObject)A, obj, name));
201:   PetscFunctionReturn(PETSC_SUCCESS);
202: }

204: /*@
205:   MatCoarsenView - Prints the coarsen data structure.

207:   Collective

209:   Input Parameters:
210: + agg    - the coarsen context
211: - viewer - optional visualization context

213:    For viewing the options database see `MatCoarsenViewFromOptions()`

215:   Level: advanced

217: .seealso: `MatCoarsen`, `PetscViewer`, `PetscViewerASCIIOpen()`, `MatCoarsenViewFromOptions`
218: @*/
219: PetscErrorCode MatCoarsenView(MatCoarsen agg, PetscViewer viewer)
220: {
221:   PetscBool isascii;

223:   PetscFunctionBegin;
225:   if (!viewer) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)agg), &viewer));
227:   PetscCheckSameComm(agg, 1, viewer, 2);

229:   PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
230:   PetscCall(PetscObjectPrintClassNamePrefixType((PetscObject)agg, viewer));
231:   if (agg->ops->view) {
232:     PetscCall(PetscViewerASCIIPushTab(viewer));
233:     PetscUseTypeMethod(agg, view, viewer);
234:     PetscCall(PetscViewerASCIIPopTab(viewer));
235:   }
236:   if (agg->strength_index_size > 0) PetscCall(PetscViewerASCIIPrintf(viewer, " Using scalar strength-of-connection index[%" PetscInt_FMT "] = {%" PetscInt_FMT ", ..}\n", agg->strength_index_size, agg->strength_index[0]));
237:   PetscFunctionReturn(PETSC_SUCCESS);
238: }

240: /*@
241:   MatCoarsenSetType - Sets the type of aggregator to use

243:   Collective

245:   Input Parameters:
246: + coarser - the coarsen context.
247: - type    - a known coarsening method

249:   Options Database Key:
250: . -mat_coarsen_type  type - maximal independent set based; distance k MIS; heavy edge matching

252:   Level: advanced

254: .seealso: `MatCoarsen`, `MatCoarsenCreate()`, `MatCoarsenApply()`, `MatCoarsenType`, `MatCoarsenGetType()`
255: @*/
256: PetscErrorCode MatCoarsenSetType(MatCoarsen coarser, MatCoarsenType type)
257: {
258:   PetscBool match;
259:   PetscErrorCode (*r)(MatCoarsen);

261:   PetscFunctionBegin;
263:   PetscAssertPointer(type, 2);

265:   PetscCall(PetscObjectTypeCompare((PetscObject)coarser, type, &match));
266:   if (match) PetscFunctionReturn(PETSC_SUCCESS);

268:   PetscTryTypeMethod(coarser, destroy);
269:   coarser->ops->destroy = NULL;
270:   PetscCall(PetscMemzero(coarser->ops, sizeof(struct _MatCoarsenOps)));

272:   PetscCall(PetscFunctionListFind(MatCoarsenList, type, &r));
273:   PetscCheck(r, PetscObjectComm((PetscObject)coarser), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unknown coarsen type %s", type);
274:   PetscCall((*r)(coarser));

276:   PetscCall(PetscFree(((PetscObject)coarser)->type_name));
277:   PetscCall(PetscStrallocpy(type, &((PetscObject)coarser)->type_name));
278:   PetscFunctionReturn(PETSC_SUCCESS);
279: }

281: /*@
282:   MatCoarsenSetGreedyOrdering - Sets the ordering of the vertices to use with a greedy coarsening method

284:   Logically Collective

286:   Input Parameters:
287: + coarser - the coarsen context
288: - perm    - vertex ordering of (greedy) algorithm

290:   Level: advanced

292:   Note:
293:   The `IS` weights is freed by PETSc, the user should not destroy it or change it after this call

295: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenCreate()`, `MatCoarsenSetType()`
296: @*/
297: PetscErrorCode MatCoarsenSetGreedyOrdering(MatCoarsen coarser, const IS perm)
298: {
299:   PetscFunctionBegin;
301:   coarser->perm = perm;
302:   PetscFunctionReturn(PETSC_SUCCESS);
303: }

305: /*@
306:   MatCoarsenGetData - Gets the weights for vertices for a coarsener.

308:   Logically Collective, No Fortran Support

310:   Input Parameter:
311: . coarser - the coarsen context

313:   Output Parameter:
314: . llist - linked list of aggregates

316:   Level: advanced

318:   Note:
319:   This passes ownership to the caller and nullifies the value of weights (`PetscCoarsenData`) within the `MatCoarsen`

321: .seealso: `MatCoarsen`, `MatCoarsenApply()`, `MatCoarsenCreate()`, `MatCoarsenSetType()`, `PetscCoarsenData`
322: @*/
323: PetscErrorCode MatCoarsenGetData(MatCoarsen coarser, PetscCoarsenData **llist)
324: {
325:   PetscFunctionBegin;
327:   PetscCheck(coarser->agg_lists, PetscObjectComm((PetscObject)coarser), PETSC_ERR_ARG_WRONGSTATE, "No linked list - generate it or call ApplyCoarsen");
328:   *llist             = coarser->agg_lists;
329:   coarser->agg_lists = NULL; /* giving up ownership */
330:   PetscFunctionReturn(PETSC_SUCCESS);
331: }

333: /*@
334:   MatCoarsenSetFromOptions - Sets various coarsen options from the options database.

336:   Collective

338:   Input Parameter:
339: . coarser - the coarsen context.

341:   Options Database Key:
342: + -mat_coarsen_type  (mis|hem|misk) - see `MatCoarsenType`
343: . -mat_coarsen_max_it its           - number of iterations to use in the coarsening process, see `MatCoarsenSetMaximumIterations()`
344: - -mat_coarsen_threshold threshold  - see `MatCoarsenSetThreshold()`, for `MATCOARSENHEM` only

346:   Level: advanced

348:   Notes:
349:   When the coarsening is used inside `PCGAMG` then the options database keys are prefixed with `-pc_gamg_`

351:   Sets the `MatCoarsenType` to `MATCOARSENMISK` if has not been set previously

353: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenApply()`, `MatCoarsenCreate()`, `MatCoarsenSetType()`,
354:           `MatCoarsenSetMaximumIterations()`, `MATCOARSENHEM`, `MATCOARSENMIS`, `MATCOARSENMISK`
355: @*/
356: PetscErrorCode MatCoarsenSetFromOptions(MatCoarsen coarser)
357: {
358:   PetscBool   flag;
359:   char        type[256];
360:   const char *def;

362:   PetscFunctionBegin;
363:   PetscObjectOptionsBegin((PetscObject)coarser);
364:   if (!((PetscObject)coarser)->type_name) {
365:     def = MATCOARSENMISK;
366:   } else {
367:     def = ((PetscObject)coarser)->type_name;
368:   }
369:   PetscCall(PetscOptionsFList("-mat_coarsen_type", "Type of aggregator", "MatCoarsenSetType", MatCoarsenList, def, type, sizeof(type), &flag));
370:   if (flag) PetscCall(MatCoarsenSetType(coarser, type));

372:   PetscCall(PetscOptionsInt("-mat_coarsen_max_it", "Number of iterations (for HEM)", "MatCoarsenSetMaximumIterations", coarser->max_it, &coarser->max_it, NULL));
373:   PetscCall(PetscOptionsReal("-mat_coarsen_threshold", "Threshold (for HEM)", "MatCoarsenSetThreshold", coarser->threshold, &coarser->threshold, NULL));
374:   coarser->strength_index_size = MAT_COARSEN_STRENGTH_INDEX_SIZE;
375:   PetscCall(PetscOptionsIntArray("-mat_coarsen_strength_index", "Array of indices to use strength of connection measure (default is all indices)", "MatCoarsenSetStrengthIndex", coarser->strength_index, &coarser->strength_index_size, NULL));
376:   /*
377:    Set the type if it was never set.
378:    */
379:   if (!((PetscObject)coarser)->type_name) PetscCall(MatCoarsenSetType(coarser, def));

381:   PetscTryTypeMethod(coarser, setfromoptions, PetscOptionsObject);
382:   PetscOptionsEnd();
383:   PetscFunctionReturn(PETSC_SUCCESS);
384: }

386: /*@
387:   MatCoarsenSetMaximumIterations - Maximum `MATCOARSENHEM` iterations to use

389:   Logically Collective

391:   Input Parameters:
392: + coarse - the coarsen context
393: - n      - number of HEM iterations

395:   Options Database Key:
396: . -mat_coarsen_max_it n - Maximum `MATCOARSENHEM` iterations to use

398:   Level: intermediate

400:   Note:
401:   When the coarsening is used inside `PCGAMG` then the options database keys are prefixed with `-pc_gamg_`

403: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenApply()`, `MatCoarsenCreate()`, `MatCoarsenSetType()`
404: @*/
405: PetscErrorCode MatCoarsenSetMaximumIterations(MatCoarsen coarse, PetscInt n)
406: {
407:   PetscFunctionBegin;
410:   PetscTryMethod(coarse, "MatCoarsenSetMaximumIterations_C", (MatCoarsen, PetscInt), (coarse, n));
411:   PetscFunctionReturn(PETSC_SUCCESS);
412: }

414: static PetscErrorCode MatCoarsenSetMaximumIterations_MATCOARSEN(MatCoarsen coarse, PetscInt b)
415: {
416:   PetscFunctionBegin;
417:   coarse->max_it = b;
418:   PetscFunctionReturn(PETSC_SUCCESS);
419: }

421: /*@
422:   MatCoarsenSetStrengthIndex -  Index array to use for index to use for strength of connection

424:   Logically Collective

426:   Input Parameters:
427: + coarse - the coarsen context
428: . n      - number of indices
429: - idx    - array of indices

431:   Options Database Key:
432: . -mat_coarsen_strength_index - array of subset of variables per vertex to use for strength norm, -1 for using all (default)

434:   Level: intermediate

436:   Note:
437:   When the coarsening is used inside `PCGAMG` then the options database keys are prefixed with `-pc_gamg_`

439: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenApply()`, `MatCoarsenCreate()`, `MatCoarsenSetType()`
440: @*/
441: PetscErrorCode MatCoarsenSetStrengthIndex(MatCoarsen coarse, PetscInt n, PetscInt idx[])
442: {
443:   PetscFunctionBegin;
446:   PetscTryMethod(coarse, "MatCoarsenSetStrengthIndex_C", (MatCoarsen, PetscInt, PetscInt[]), (coarse, n, idx));
447:   PetscFunctionReturn(PETSC_SUCCESS);
448: }

450: static PetscErrorCode MatCoarsenSetStrengthIndex_MATCOARSEN(MatCoarsen coarse, PetscInt n, PetscInt idx[])
451: {
452:   PetscFunctionBegin;
453:   coarse->strength_index_size = n;
454:   for (int iii = 0; iii < n; iii++) coarse->strength_index[iii] = idx[iii];
455:   PetscFunctionReturn(PETSC_SUCCESS);
456: }

458: /*@
459:   MatCoarsenSetThreshold - Set the threshold for HEM

461:   Logically Collective

463:   Input Parameters:
464: + coarse - the coarsen context
465: - b      - threshold value, default is 0

467:   Options Database Key:
468: . -mat_coarsen_threshold b - threshold

470:   Level: intermediate

472:   Note:
473:   When the coarsening is used inside `PCGAMG` then the options database keys are prefixed with `-pc_gamg_`

475:   Developer Note:
476:   It is not documented how this threshold is used

478: .seealso: `MatCoarsen`, `MatCoarsenType`, `MatCoarsenApply()`, `MatCoarsenCreate()`, `MatCoarsenSetType()`
479: @*/
480: PetscErrorCode MatCoarsenSetThreshold(MatCoarsen coarse, PetscReal b)
481: {
482:   PetscFunctionBegin;
485:   PetscTryMethod(coarse, "MatCoarsenSetThreshold_C", (MatCoarsen, PetscReal), (coarse, b));
486:   PetscFunctionReturn(PETSC_SUCCESS);
487: }

489: static PetscErrorCode MatCoarsenSetThreshold_MATCOARSEN(MatCoarsen coarse, PetscReal b)
490: {
491:   PetscFunctionBegin;
492:   coarse->threshold = b;
493:   PetscFunctionReturn(PETSC_SUCCESS);
494: }

496: /*@
497:   MatCoarsenCreate - Creates a coarsen context.

499:   Collective

501:   Input Parameter:
502: . comm - MPI communicator

504:   Output Parameter:
505: . newcrs - location to put the context

507:   Level: advanced

509: .seealso: `MatCoarsen`, `MatCoarsenSetType()`, `MatCoarsenApply()`, `MatCoarsenDestroy()`,
510:           `MatCoarsenSetAdjacency()`, `MatCoarsenGetData()`
511: @*/
512: PetscErrorCode MatCoarsenCreate(MPI_Comm comm, MatCoarsen *newcrs)
513: {
514:   MatCoarsen agg;

516:   PetscFunctionBegin;
517:   PetscAssertPointer(newcrs, 2);
518:   PetscCall(MatInitializePackage());

520:   PetscCall(PetscHeaderCreate(agg, MAT_COARSEN_CLASSID, "MatCoarsen", "Matrix/graph coarsen", "MatCoarsen", comm, MatCoarsenDestroy, MatCoarsenView));
521:   PetscCall(PetscObjectComposeFunction((PetscObject)agg, "MatCoarsenSetMaximumIterations_C", MatCoarsenSetMaximumIterations_MATCOARSEN));
522:   PetscCall(PetscObjectComposeFunction((PetscObject)agg, "MatCoarsenSetThreshold_C", MatCoarsenSetThreshold_MATCOARSEN));
523:   PetscCall(PetscObjectComposeFunction((PetscObject)agg, "MatCoarsenSetStrengthIndex_C", MatCoarsenSetStrengthIndex_MATCOARSEN));
524:   agg->strength_index_size = 0;
525:   *newcrs                  = agg;
526:   PetscFunctionReturn(PETSC_SUCCESS);
527: }