Actual source code: matcoloring.c
petsc-3.8.4 2018-03-24
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: .keywords: matrix, Coloring, register
30: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
31: @*/
32: PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
33: {
37: PetscFunctionListAdd(&MatColoringList,sname,function);
38: return(0);
39: }
41: /*@
42: MatColoringCreate - Creates a matrix coloring context.
44: Collective on MatColoring
46: Input Parameters:
47: . comm - MPI communicator
49: Output Parameter:
50: . mcptr - the new MatColoring context
52: Options Database Keys:
53: + -mat_coloring_type - the type of coloring algorithm used
54: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
55: . -mat_coloring_distance - compute a distance 1,2,... coloring.
56: . -mat_coloring_view - print information about the coloring and the produced index sets
57: - -mat_coloring_valid - debugging option that prints all coloring incompatibilities
59: Level: beginner
61: .keywords: Coloring, Matrix
63: .seealso: MatColoring, MatColoringApply()
64: @*/
65: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
66: {
67: MatColoring mc;
73: *mcptr = NULL;
75: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
76: MatInitializePackage();
77: #endif
78: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
79: 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: return(0);
89: }
92: /*@
93: MatColoringDestroy - Destroys the matrix coloring context
95: Collective on MatColoring
97: Input Parameter:
98: . mc - the MatColoring context
100: Level: beginner
102: .keywords: Coloring, destroy
104: .seealso: MatColoringCreate(), MatColoringApply()
105: @*/
106: PetscErrorCode MatColoringDestroy(MatColoring *mc)
107: {
111: if (--((PetscObject)(*mc))->refct > 0) {*mc = 0; return(0);}
112: MatDestroy(&(*mc)->mat);
113: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
114: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
115: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
116: PetscHeaderDestroy(mc);
117: return(0);
118: }
120: /*@C
121: MatColoringSetType - Sets the type of coloring algorithm used
123: Collective on MatColoring
125: Input Parameter:
126: + mc - the MatColoring context
127: - type - the type of coloring
129: Level: beginner
131: Notes: Possible types include the sequential types MATCOLORINGLF,
132: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
133: as a parallel MATCOLORINGMIS algorithm.
135: .keywords: Coloring, type
137: .seealso: MatColoringCreate(), MatColoringApply()
138: @*/
139: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
140: {
141: PetscBool match;
142: PetscErrorCode ierr,(*r)(MatColoring);
147: PetscObjectTypeCompare((PetscObject)mc,type,&match);
148: if (match) return(0);
149: PetscFunctionListFind(MatColoringList,type,&r);
150: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
151: if (mc->ops->destroy) {
152: (*(mc)->ops->destroy)(mc);
153: mc->ops->destroy = NULL;
154: }
155: mc->ops->apply = 0;
156: mc->ops->view = 0;
157: mc->ops->setfromoptions = 0;
158: mc->ops->destroy = 0;
160: PetscObjectChangeTypeName((PetscObject)mc,type);
161: (*r)(mc);
162: return(0);
163: }
165: /*@
166: MatColoringSetFromOptions - Sets MatColoring options from user parameters
168: Collective on MatColoring
170: Input Parameters:
171: . mc - MatColoring context
173: Options Database Keys:
174: + -mat_coloring_type - the type of coloring algorithm used
175: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
176: . -mat_coloring_distance - compute a distance 1,2,... coloring.
177: . -mat_coloring_view - print information about the coloring and the produced index sets
179: Level: beginner
181: .keywords: Coloring, Matrix
183: .seealso: MatColoring, MatColoringApply()
184: @*/
185: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
186: {
187: PetscBool flg;
188: MatColoringType deft = MATCOLORINGSL;
189: char type[256];
191: PetscInt dist,maxcolors;
195: MatColoringGetDistance(mc,&dist);
196: if (dist == 2) deft = MATCOLORINGSL;
197: else deft = MATCOLORINGGREEDY;
198: MatColoringGetMaxColors(mc,&maxcolors);
199: MatColoringRegisterAll();
200: PetscObjectOptionsBegin((PetscObject)mc);
201: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
202: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
203: if (flg) {
204: MatColoringSetType(mc,type);
205: } else if (!((PetscObject)mc)->type_name) {
206: MatColoringSetType(mc,deft);
207: }
208: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
209: if (flg) {MatColoringSetDistance(mc,dist);}
210: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
211: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
212: if (mc->ops->setfromoptions) {
213: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
214: }
215: PetscOptionsBool("-mat_coloring_valid","Check that a valid coloring has been produced","",mc->valid,&mc->valid,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 Parameter:
228: . mc - the MatColoring context
229: . dist - the distance the coloring should compute
231: Level: beginner
233: Notes: 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: .keywords: Coloring, distance, Jacobian
241: .seealso: MatColoringGetDistance(), MatColoringApply()
242: @*/
243: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
244: {
247: mc->dist = dist;
248: return(0);
249: }
251: /*@
252: MatColoringGetDistance - Gets the distance of the coloring
254: Logically Collective on MatColoring
256: Input Parameter:
257: . mc - the MatColoring context
259: Output Paramter:
260: . dist - the current distance being used for the coloring.
262: Level: beginner
264: .keywords: Coloring, distance
266: .seealso: MatColoringSetDistance(), MatColoringApply()
267: @*/
268: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
269: {
272: if (dist) *dist = mc->dist;
273: return(0);
274: }
276: /*@
277: MatColoringSetMaxColors - Sets the maximum number of colors
279: Logically Collective on MatColoring
281: Input Parameter:
282: + mc - the MatColoring context
283: - maxcolors - the maximum number of colors to produce
285: Level: beginner
287: Notes: This may be used to compute a certain number of
288: independent sets from the graph. For instance, while using
289: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
290: not in a color are set to have color maxcolors+1, which is not
291: a valid color as they may be adjacent.
293: .keywords: Coloring
295: .seealso: MatColoringGetMaxColors(), MatColoringApply()
296: @*/
297: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
298: {
301: mc->maxcolors = maxcolors;
302: return(0);
303: }
305: /*@
306: MatColoringGetMaxColors - Gets the maximum number of colors
308: Logically Collective on MatColoring
310: Input Parameter:
311: . mc - the MatColoring context
313: Output Paramter:
314: . maxcolors - the current maximum number of colors to produce
316: Level: beginner
318: .keywords: Coloring
320: .seealso: MatColoringSetMaxColors(), MatColoringApply()
321: @*/
322: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
323: {
326: if (maxcolors) *maxcolors = mc->maxcolors;
327: return(0);
328: }
330: /*@
331: MatColoringApply - Apply the coloring to the matrix, producing index
332: sets corresponding to a number of independent sets in the induced
333: graph.
335: Collective on MatColoring
337: Input Parameters:
338: . mc - the MatColoring context
340: Output Parameter:
341: . coloring - the ISColoring instance containing the coloring
343: Level: beginner
345: .keywords: Coloring, Apply
347: .seealso: MatColoring, MatColoringCreate()
348: @*/
349: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
350: {
351: PetscErrorCode ierr;
352: PetscBool flg;
353: PetscViewerFormat format;
354: PetscViewer viewer;
355: PetscInt nc,ncolors;
359: PetscLogEventBegin(MATCOLORING_Apply,mc,0,0,0);
360: (*mc->ops->apply)(mc,coloring);
361: PetscLogEventEnd(MATCOLORING_Apply,mc,0,0,0);
362: /* valid */
363: if (mc->valid) {
364: MatColoringTestValid(mc,*coloring);
365: }
366: /* view */
367: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
368: if (flg && !PetscPreLoadingOn) {
369: PetscViewerPushFormat(viewer,format);
370: MatColoringView(mc,viewer);
371: MatGetSize(mc->mat,NULL,&nc);
372: ISColoringGetIS(*coloring,&ncolors,NULL);
373: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
374: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
375: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
376: PetscViewerPopFormat(viewer);
377: PetscViewerDestroy(&viewer);
378: }
379: return(0);
380: }
382: /*@
383: MatColoringView - Output details about the MatColoring.
385: Collective on MatColoring
387: Input Parameters:
388: - mc - the MatColoring context
389: + viewer - the Viewer context
391: Level: beginner
393: .keywords: Coloring, view
395: .seealso: MatColoring, MatColoringApply()
396: @*/
397: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
398: {
400: PetscBool iascii;
404: if (!viewer) {
405: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
406: }
410: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
411: if (iascii) {
412: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
413: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
414: if (mc->maxcolors > 0) {
415: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
416: } else {
417: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
418: }
419: }
420: return(0);
421: }
423: /*@
424: MatColoringSetWeightType - Set the type of weight computation used.
426: Logically collective on MatColoring
428: Input Parameters:
429: - mc - the MatColoring context
430: + wt - the weight type
432: Level: beginner
434: .keywords: Coloring, view
436: .seealso: MatColoring, MatColoringWeightType
437: @*/
438: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
439: {
441: mc->weight_type = wt;
442: return(0);
444: }