Actual source code: matcoloring.c
petsc-3.12.5 2020-03-29
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: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
29: @*/
30: PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
31: {
35: MatInitializePackage();
36: PetscFunctionListAdd(&MatColoringList,sname,function);
37: return(0);
38: }
40: /*@
41: MatColoringCreate - Creates a matrix coloring context.
43: Collective on MatColoring
45: Input Parameters:
46: . comm - MPI communicator
48: Output Parameter:
49: . mcptr - the new MatColoring context
51: Options Database Keys:
52: + -mat_coloring_type - the type of coloring algorithm used
53: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
54: . -mat_coloring_distance - compute a distance 1,2,... coloring.
55: . -mat_coloring_view - print information about the coloring and the produced index sets
56: . -mat_coloring_test - debugging option that prints all coloring incompatibilities
57: - -mat_is_coloring_test - debugging option that throws an error if MatColoringApply() generates an incorrect iscoloring
59: Level: beginner
61: Notes:
62: A distance one coloring is useful, for example, multi-color SOR. A distance two coloring is for the finite difference computation of Jacobians
63: (see MatFDColoringCreate()).
65: Some coloring types only support distance two colorings
67: .seealso: MatColoring, MatColoringApply(), MatFDColoringCreate()
68: @*/
69: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
70: {
71: MatColoring mc;
77: *mcptr = NULL;
79: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
80: MatInitializePackage();
81: #endif
82: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
83: PetscObjectReference((PetscObject)m);
84: mc->mat = m;
85: mc->dist = 2; /* default to Jacobian computation case */
86: mc->maxcolors = IS_COLORING_MAX;
87: *mcptr = mc;
88: mc->valid = PETSC_FALSE;
89: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
90: mc->user_weights = NULL;
91: mc->user_lperm = NULL;
92: return(0);
93: }
96: /*@
97: MatColoringDestroy - Destroys the matrix coloring context
99: Collective on MatColoring
101: Input Parameter:
102: . mc - the MatColoring context
104: Level: beginner
106: .seealso: MatColoringCreate(), MatColoringApply()
107: @*/
108: PetscErrorCode MatColoringDestroy(MatColoring *mc)
109: {
113: if (--((PetscObject)(*mc))->refct > 0) {*mc = 0; return(0);}
114: MatDestroy(&(*mc)->mat);
115: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
116: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
117: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
118: PetscHeaderDestroy(mc);
119: return(0);
120: }
122: /*@C
123: MatColoringSetType - Sets the type of coloring algorithm used
125: Collective on MatColoring
127: Input Parameter:
128: + mc - the MatColoring context
129: - type - the type of coloring
131: Level: beginner
133: Notes:
134: Possible types include the sequential types MATCOLORINGLF,
135: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
136: as a parallel MATCOLORINGMIS algorithm.
138: .seealso: MatColoringCreate(), MatColoringApply()
139: @*/
140: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
141: {
142: PetscBool match;
143: PetscErrorCode ierr,(*r)(MatColoring);
148: PetscObjectTypeCompare((PetscObject)mc,type,&match);
149: if (match) return(0);
150: PetscFunctionListFind(MatColoringList,type,&r);
151: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
152: if (mc->ops->destroy) {
153: (*(mc)->ops->destroy)(mc);
154: mc->ops->destroy = NULL;
155: }
156: mc->ops->apply = 0;
157: mc->ops->view = 0;
158: mc->ops->setfromoptions = 0;
159: mc->ops->destroy = 0;
161: PetscObjectChangeTypeName((PetscObject)mc,type);
162: (*r)(mc);
163: return(0);
164: }
166: /*@
167: MatColoringSetFromOptions - Sets MatColoring options from user parameters
169: Collective on MatColoring
171: Input Parameters:
172: . mc - MatColoring context
174: Options Database Keys:
175: + -mat_coloring_type - the type of coloring algorithm used
176: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
177: . -mat_coloring_distance - compute a distance 1,2,... coloring.
178: - -mat_coloring_view - print information about the coloring and the produced index sets
180: Level: beginner
182: .seealso: MatColoring, MatColoringApply()
183: @*/
184: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
185: {
186: PetscBool flg;
187: MatColoringType deft = MATCOLORINGSL;
188: char type[256];
190: PetscInt dist,maxcolors;
194: MatColoringGetDistance(mc,&dist);
195: if (dist == 2) deft = MATCOLORINGSL;
196: else deft = MATCOLORINGGREEDY;
197: MatColoringGetMaxColors(mc,&maxcolors);
198: MatColoringRegisterAll();
199: PetscObjectOptionsBegin((PetscObject)mc);
200: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
201: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
202: if (flg) {
203: MatColoringSetType(mc,type);
204: } else if (!((PetscObject)mc)->type_name) {
205: MatColoringSetType(mc,deft);
206: }
207: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
208: if (flg) {MatColoringSetDistance(mc,dist);}
209: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
210: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
211: if (mc->ops->setfromoptions) {
212: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
213: }
214: PetscOptionsBool("-mat_coloring_test","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
215: PetscOptionsBool("-mat_is_coloring_test","Check that a valid iscoloring has been produced","",mc->valid_iscoloring,&mc->valid_iscoloring,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 Parameters:
228: + mc - the MatColoring context
229: - dist - the distance the coloring should compute
231: Level: beginner
233: Notes:
234: The distance of the coloring denotes the minimum number
235: of edges in the graph induced by the matrix any two vertices
236: of the same color are. Distance-1 colorings are the classical
237: coloring, where no two vertices of the same color are adjacent.
238: distance-2 colorings are useful for the computation of Jacobians.
240: .seealso: MatColoringGetDistance(), MatColoringApply()
241: @*/
242: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
243: {
246: mc->dist = dist;
247: return(0);
248: }
250: /*@
251: MatColoringGetDistance - Gets the distance of the coloring
253: Logically Collective on MatColoring
255: Input Parameter:
256: . mc - the MatColoring context
258: Output Paramter:
259: . dist - the current distance being used for the coloring.
261: Level: beginner
263: .seealso: MatColoringSetDistance(), MatColoringApply()
264: @*/
265: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
266: {
269: if (dist) *dist = mc->dist;
270: return(0);
271: }
273: /*@
274: MatColoringSetMaxColors - Sets the maximum number of colors
276: Logically Collective on MatColoring
278: Input Parameter:
279: + mc - the MatColoring context
280: - maxcolors - the maximum number of colors to produce
282: Level: beginner
284: Notes:
285: This may be used to compute a certain number of
286: independent sets from the graph. For instance, while using
287: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
288: not in a color are set to have color maxcolors+1, which is not
289: a valid color as they may be adjacent.
291: .seealso: MatColoringGetMaxColors(), MatColoringApply()
292: @*/
293: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
294: {
297: mc->maxcolors = maxcolors;
298: return(0);
299: }
301: /*@
302: MatColoringGetMaxColors - Gets the maximum number of colors
304: Logically Collective on MatColoring
306: Input Parameter:
307: . mc - the MatColoring context
309: Output Paramter:
310: . maxcolors - the current maximum number of colors to produce
312: Level: beginner
314: .seealso: MatColoringSetMaxColors(), MatColoringApply()
315: @*/
316: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
317: {
320: if (maxcolors) *maxcolors = mc->maxcolors;
321: return(0);
322: }
324: /*@
325: MatColoringApply - Apply the coloring to the matrix, producing index
326: sets corresponding to a number of independent sets in the induced
327: graph.
329: Collective on MatColoring
331: Input Parameters:
332: . mc - the MatColoring context
334: Output Parameter:
335: . coloring - the ISColoring instance containing the coloring
337: Level: beginner
339: .seealso: MatColoring, MatColoringCreate()
340: @*/
341: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
342: {
343: PetscErrorCode ierr;
344: PetscBool flg;
345: PetscViewerFormat format;
346: PetscViewer viewer;
347: PetscInt nc,ncolors;
351: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
352: (*mc->ops->apply)(mc,coloring);
353: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
355: /* valid */
356: if (mc->valid) {
357: MatColoringTest(mc,*coloring);
358: }
359: if (mc->valid_iscoloring) {
360: MatISColoringTest(mc->mat,*coloring);
361: }
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 %d\n",ncolors);
371: PetscViewerASCIIPrintf(viewer," Number of total columns %d\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 MatColoring
384: Input Parameters:
385: - mc - the MatColoring context
386: + viewer - the Viewer context
388: Level: beginner
390: .seealso: MatColoring, MatColoringApply()
391: @*/
392: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
393: {
395: PetscBool iascii;
399: if (!viewer) {
400: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
401: }
405: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
406: if (iascii) {
407: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
408: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
409: if (mc->maxcolors > 0) {
410: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
411: } else {
412: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
413: }
414: }
415: return(0);
416: }
418: /*@
419: MatColoringSetWeightType - Set the type of weight computation used.
421: Logically collective on MatColoring
423: Input Parameters:
424: - mc - the MatColoring context
425: + wt - the weight type
427: Level: beginner
429: .seealso: MatColoring, MatColoringWeightType
430: @*/
431: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
432: {
434: mc->weight_type = wt;
435: return(0);
437: }