Actual source code: matcoloring.c
petsc-3.7.5 2017-01-01
1: #include <petsc/private/matimpl.h> /*I "petscmat.h" I*/
3: PetscFunctionList MatColoringList = 0;
4: PetscBool MatColoringRegisterAllCalled = PETSC_FALSE;
5: const char *const MatColoringWeightTypes[] = {"RANDOM","LEXICAL","LF","SL","MatColoringWeightType","MAT_COLORING_WEIGHT_",0};
7: PETSC_EXTERN PetscErrorCode MatColoringTestValid(MatColoring,ISColoring);
11: /*@C
12: MatColoringRegister - Adds a new sparse matrix coloring to the matrix package.
14: Not Collective
16: Input Parameters:
17: + sname - name of Coloring (for example MATCOLORINGSL)
18: - function - function pointer that creates the coloring
20: Level: developer
22: Sample usage:
23: .vb
24: MatColoringRegister("my_color",MyColor);
25: .ve
27: Then, your partitioner can be chosen with the procedural interface via
28: $ MatColoringSetType(part,"my_color")
29: or at runtime via the option
30: $ -mat_coloring_type my_color
32: .keywords: matrix, Coloring, register
34: .seealso: MatColoringRegisterDestroy(), MatColoringRegisterAll()
35: @*/
36: PetscErrorCode MatColoringRegister(const char sname[],PetscErrorCode (*function)(MatColoring))
37: {
41: PetscFunctionListAdd(&MatColoringList,sname,function);
42: return(0);
43: }
47: /*@
48: MatColoringCreate - Creates a matrix coloring context.
50: Collective on MatColoring
52: Input Parameters:
53: . comm - MPI communicator
55: Output Parameter:
56: . mcptr - the new MatColoring context
58: Options Database Keys:
59: + -mat_coloring_type - the type of coloring algorithm used
60: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
61: . -mat_coloring_distance - compute a distance 1,2,... coloring.
62: . -mat_coloring_view - print information about the coloring and the produced index sets
63: - -mat_coloring_valid - debugging option that prints all coloring incompatibilities
65: Level: beginner
67: .keywords: Coloring, Matrix
69: .seealso: MatColoring, MatColoringApply()
70: @*/
71: PetscErrorCode MatColoringCreate(Mat m,MatColoring *mcptr)
72: {
73: MatColoring mc;
79: *mcptr = NULL;
81: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
82: MatInitializePackage();
83: #endif
84: PetscHeaderCreate(mc, MAT_COLORING_CLASSID,"MatColoring","Matrix coloring", "MatColoring",PetscObjectComm((PetscObject)m),MatColoringDestroy, MatColoringView);
85: PetscObjectReference((PetscObject)m);
86: mc->mat = m;
87: mc->dist = 2; /* default to Jacobian computation case */
88: mc->maxcolors = IS_COLORING_MAX;
89: *mcptr = mc;
90: mc->valid = PETSC_FALSE;
91: mc->weight_type = MAT_COLORING_WEIGHT_RANDOM;
92: mc->user_weights = NULL;
93: mc->user_lperm = NULL;
94: return(0);
95: }
100: /*@
101: MatColoringDestroy - Destroys the matrix coloring context
103: Collective on MatColoring
105: Input Parameter:
106: . mc - the MatColoring context
108: Level: beginner
110: .keywords: Coloring, destroy
112: .seealso: MatColoringCreate(), MatColoringApply()
113: @*/
114: PetscErrorCode MatColoringDestroy(MatColoring *mc)
115: {
119: if (--((PetscObject)(*mc))->refct > 0) {*mc = 0; return(0);}
120: MatDestroy(&(*mc)->mat);
121: if ((*mc)->ops->destroy) {(*((*mc)->ops->destroy))(*mc);}
122: if ((*mc)->user_weights) {PetscFree((*mc)->user_weights);}
123: if ((*mc)->user_lperm) {PetscFree((*mc)->user_lperm);}
124: PetscHeaderDestroy(mc);
125: return(0);
126: }
130: /*@C
131: MatColoringSetType - Sets the type of coloring algorithm used
133: Collective on MatColoring
135: Input Parameter:
136: + mc - the MatColoring context
137: - type - the type of coloring
139: Level: beginner
141: Notes: Possible types include the sequential types MATCOLORINGLF,
142: MATCOLORINGSL, and MATCOLORINGID from the MINPACK package as well
143: as a parallel MATCOLORINGMIS algorithm.
145: .keywords: Coloring, type
147: .seealso: MatColoringCreate(), MatColoringApply()
148: @*/
149: PetscErrorCode MatColoringSetType(MatColoring mc,MatColoringType type)
150: {
151: PetscBool match;
152: PetscErrorCode ierr,(*r)(MatColoring);
157: PetscObjectTypeCompare((PetscObject)mc,type,&match);
158: if (match) return(0);
159: PetscFunctionListFind(MatColoringList,type,&r);
160: if (!r) SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unable to find requested MatColoring type %s",type);
161: if (mc->ops->destroy) {
162: (*(mc)->ops->destroy)(mc);
163: mc->ops->destroy = NULL;
164: }
165: mc->ops->apply = 0;
166: mc->ops->view = 0;
167: mc->ops->setfromoptions = 0;
168: mc->ops->destroy = 0;
170: PetscObjectChangeTypeName((PetscObject)mc,type);
171: (*r)(mc);
172: return(0);
173: }
177: /*@
178: MatColoringSetFromOptions - Sets MatColoring options from user parameters
180: Collective on MatColoring
182: Input Parameters:
183: . mc - MatColoring context
185: Options Database Keys:
186: + -mat_coloring_type - the type of coloring algorithm used
187: . -mat_coloring_maxcolors - the maximum number of relevant colors, all nodes not in a color are in maxcolors+1
188: . -mat_coloring_distance - compute a distance 1,2,... coloring.
189: . -mat_coloring_view - print information about the coloring and the produced index sets
191: Level: beginner
193: .keywords: Coloring, Matrix
195: .seealso: MatColoring, MatColoringApply()
196: @*/
197: PetscErrorCode MatColoringSetFromOptions(MatColoring mc)
198: {
199: PetscBool flg;
200: MatColoringType deft = MATCOLORINGSL;
201: char type[256];
203: PetscInt dist,maxcolors;
207: MatColoringGetDistance(mc,&dist);
208: if (dist == 2) deft = MATCOLORINGSL;
209: else deft = MATCOLORINGGREEDY;
210: MatColoringGetMaxColors(mc,&maxcolors);
211: MatColoringRegisterAll();
212: PetscObjectOptionsBegin((PetscObject)mc);
213: if (((PetscObject)mc)->type_name) deft = ((PetscObject)mc)->type_name;
214: PetscOptionsFList("-mat_coloring_type","The coloring method used","MatColoringSetType",MatColoringList,deft,type,256,&flg);
215: if (flg) {
216: MatColoringSetType(mc,type);
217: } else if (!((PetscObject)mc)->type_name) {
218: MatColoringSetType(mc,deft);
219: }
220: PetscOptionsInt("-mat_coloring_distance","Distance of the coloring","MatColoringSetDistance",dist,&dist,&flg);
221: if (flg) {MatColoringSetDistance(mc,dist);}
222: PetscOptionsInt("-mat_coloring_maxcolors","Maximum colors returned at the end. 1 returns an independent set","MatColoringSetMaxColors",maxcolors,&maxcolors,&flg);
223: if (flg) {MatColoringSetMaxColors(mc,maxcolors);}
224: if (mc->ops->setfromoptions) {
225: (*mc->ops->setfromoptions)(PetscOptionsObject,mc);
226: }
227: PetscOptionsBool("-mat_coloring_valid","Check that a valid coloring has been produced","",mc->valid,&mc->valid,NULL);
228: PetscOptionsEnum("-mat_coloring_weight_type","Sets the type of vertex weighting used","MatColoringSetWeightType",MatColoringWeightTypes,(PetscEnum)mc->weight_type,(PetscEnum*)&mc->weight_type,NULL);
229: PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject)mc);
230: PetscOptionsEnd();
231: return(0);
232: }
236: /*@
237: MatColoringSetDistance - Sets the distance of the coloring
239: Logically Collective on MatColoring
241: Input Parameter:
242: . mc - the MatColoring context
243: . dist - the distance the coloring should compute
245: Level: beginner
247: Notes: The distance of the coloring denotes the minimum number
248: of edges in the graph induced by the matrix any two vertices
249: of the same color are. Distance-1 colorings are the classical
250: coloring, where no two vertices of the same color are adjacent.
251: distance-2 colorings are useful for the computation of Jacobians.
253: .keywords: Coloring, distance, Jacobian
255: .seealso: MatColoringGetDistance(), MatColoringApply()
256: @*/
257: PetscErrorCode MatColoringSetDistance(MatColoring mc,PetscInt dist)
258: {
261: mc->dist = dist;
262: return(0);
263: }
267: /*@
268: MatColoringGetDistance - Gets the distance of the coloring
270: Logically Collective on MatColoring
272: Input Parameter:
273: . mc - the MatColoring context
275: Output Paramter:
276: . dist - the current distance being used for the coloring.
278: Level: beginner
280: .keywords: Coloring, distance
282: .seealso: MatColoringSetDistance(), MatColoringApply()
283: @*/
284: PetscErrorCode MatColoringGetDistance(MatColoring mc,PetscInt *dist)
285: {
288: if (dist) *dist = mc->dist;
289: return(0);
290: }
294: /*@
295: MatColoringSetMaxColors - Sets the maximum number of colors
297: Logically Collective on MatColoring
299: Input Parameter:
300: + mc - the MatColoring context
301: - maxcolors - the maximum number of colors to produce
303: Level: beginner
305: Notes: This may be used to compute a certain number of
306: independent sets from the graph. For instance, while using
307: MATCOLORINGMIS and maxcolors = 1, one gets out an MIS. Vertices
308: not in a color are set to have color maxcolors+1, which is not
309: a valid color as they may be adjacent.
311: .keywords: Coloring
313: .seealso: MatColoringGetMaxColors(), MatColoringApply()
314: @*/
315: PetscErrorCode MatColoringSetMaxColors(MatColoring mc,PetscInt maxcolors)
316: {
319: mc->maxcolors = maxcolors;
320: return(0);
321: }
325: /*@
326: MatColoringGetMaxColors - Gets the maximum number of colors
328: Logically Collective on MatColoring
330: Input Parameter:
331: . mc - the MatColoring context
333: Output Paramter:
334: . maxcolors - the current maximum number of colors to produce
336: Level: beginner
338: .keywords: Coloring
340: .seealso: MatColoringSetMaxColors(), MatColoringApply()
341: @*/
342: PetscErrorCode MatColoringGetMaxColors(MatColoring mc,PetscInt *maxcolors)
343: {
346: if (maxcolors) *maxcolors = mc->maxcolors;
347: return(0);
348: }
352: /*@
353: MatColoringApply - Apply the coloring to the matrix, producing index
354: sets corresponding to a number of independent sets in the induced
355: graph.
357: Collective on MatColoring
359: Input Parameters:
360: . mc - the MatColoring context
362: Output Parameter:
363: . coloring - the ISColoring instance containing the coloring
365: Level: beginner
367: .keywords: Coloring, Apply
369: .seealso: MatColoring, MatColoringCreate()
370: @*/
371: PetscErrorCode MatColoringApply(MatColoring mc,ISColoring *coloring)
372: {
373: PetscErrorCode ierr;
374: PetscBool flg;
375: PetscViewerFormat format;
376: PetscViewer viewer;
377: PetscInt nc,ncolors;
381: PetscLogEventBegin(Mat_Coloring_Apply,mc,0,0,0);
382: (*mc->ops->apply)(mc,coloring);
383: PetscLogEventEnd(Mat_Coloring_Apply,mc,0,0,0);
384: /* valid */
385: if (mc->valid) {
386: MatColoringTestValid(mc,*coloring);
387: }
388: /* view */
389: PetscOptionsGetViewer(PetscObjectComm((PetscObject)mc),((PetscObject)mc)->prefix,"-mat_coloring_view",&viewer,&format,&flg);
390: if (flg && !PetscPreLoadingOn) {
391: PetscViewerPushFormat(viewer,format);
392: MatColoringView(mc,viewer);
393: MatGetSize(mc->mat,NULL,&nc);
394: ISColoringGetIS(*coloring,&ncolors,NULL);
395: PetscViewerASCIIPrintf(viewer," Number of colors %d\n",ncolors);
396: PetscViewerASCIIPrintf(viewer," Number of total columns %d\n",nc);
397: if (nc <= 1000) {ISColoringView(*coloring,viewer);}
398: PetscViewerPopFormat(viewer);
399: PetscViewerDestroy(&viewer);
400: }
401: return(0);
402: }
406: /*@
407: MatColoringView - Output details about the MatColoring.
409: Collective on MatColoring
411: Input Parameters:
412: - mc - the MatColoring context
413: + viewer - the Viewer context
415: Level: beginner
417: .keywords: Coloring, view
419: .seealso: MatColoring, MatColoringApply()
420: @*/
421: PetscErrorCode MatColoringView(MatColoring mc,PetscViewer viewer)
422: {
424: PetscBool iascii;
428: if (!viewer) {
429: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)mc),&viewer);
430: }
434: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
435: if (iascii) {
436: PetscObjectPrintClassNamePrefixType((PetscObject)mc,viewer);
437: PetscViewerASCIIPrintf(viewer," Weight type: %s\n",MatColoringWeightTypes[mc->weight_type]);
438: if (mc->maxcolors > 0) {
439: PetscViewerASCIIPrintf(viewer," Distance %D, Max. Colors %D\n",mc->dist,mc->maxcolors);
440: } else {
441: PetscViewerASCIIPrintf(viewer," Distance %d\n",mc->dist);
442: }
443: }
444: return(0);
445: }
447: /*@
448: MatColoringSetWeightType - Set the type of weight computation used.
450: Logically collective on MatColoring
452: Input Parameters:
453: - mc - the MatColoring context
454: + wt - the weight type
456: Level: beginner
458: .keywords: Coloring, view
460: .seealso: MatColoring, MatColoringWeightType
461: @*/
464: PetscErrorCode MatColoringSetWeightType(MatColoring mc,MatColoringWeightType wt)
465: {
467: mc->weight_type = wt;
468: return(0);
470: }