Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
meshpart.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * meshpart.c
5  *
6  * This file contains routines for partitioning finite element meshes.
7  *
8  * Started 9/29/97
9  * George
10  *
11  * $Id: meshpart.c,v 1.1 1998/11/27 17:59:21 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 
18 /*************************************************************************
19 * This function partitions a finite element mesh by partitioning its nodal
20 * graph using KMETIS and then assigning elements in a load balanced fashion.
21 **************************************************************************/
22 void METIS_PartMeshNodal(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag,
23  int *nparts, int *edgecut, idxtype *epart, idxtype *npart)
24 {
25  int i, j, k, me;
26  idxtype *xadj, *adjncy, *pwgts;
27  int options[10], pnumflag=0, wgtflag=0;
28  int nnbrs, nbrind[200], nbrwgt[200], maxpwgt;
29  int esize, esizes[] = {-1, 3, 4, 8, 4};
30 
31  esize = esizes[*etype];
32 
33  if (*numflag == 1)
34  ChangeMesh2CNumbering((*ne)*esize, elmnts);
35 
36  xadj = idxmalloc(*nn+1, "METIS_MESHPARTNODAL: xadj");
37  adjncy = idxmalloc(20*(*nn), "METIS_MESHPARTNODAL: adjncy");
38 
39  METIS_MeshToNodal(ne, nn, elmnts, etype, &pnumflag, xadj, adjncy);
40 
41  adjncy = realloc(adjncy, xadj[*nn]*sizeof(idxtype));
42 
43  options[0] = 0;
44  METIS_PartGraphKway(nn, xadj, adjncy, NULL, NULL, &wgtflag, &pnumflag, nparts, options, edgecut, npart);
45 
46  /* OK, now compute an element partition based on the nodal partition npart */
47  idxset(*ne, -1, epart);
48  pwgts = idxsmalloc(*nparts, 0, "METIS_MESHPARTNODAL: pwgts");
49  for (i=0; i<*ne; i++) {
50  me = npart[elmnts[i*esize]];
51  for (j=1; j<esize; j++) {
52  if (npart[elmnts[i*esize+j]] != me)
53  break;
54  }
55  if (j == esize) {
56  epart[i] = me;
57  pwgts[me]++;
58  }
59  }
60 
61  maxpwgt = 1.03*(*ne)/(*nparts);
62  for (i=0; i<*ne; i++) {
63  if (epart[i] == -1) { /* Assign the boundary element */
64  nnbrs = 0;
65  for (j=0; j<esize; j++) {
66  me = npart[elmnts[i*esize+j]];
67  for (k=0; k<nnbrs; k++) {
68  if (nbrind[k] == me) {
69  nbrwgt[k]++;
70  break;
71  }
72  }
73  if (k == nnbrs) {
74  nbrind[nnbrs] = me;
75  nbrwgt[nnbrs++] = 1;
76  }
77  }
78  /* Try to assign it first to the domain with most things in common */
79  j = iamax(nnbrs, nbrwgt);
80  if (pwgts[nbrind[j]] < maxpwgt) {
81  epart[i] = nbrind[j];
82  }
83  else {
84  /* If that fails, assign it to a light domain */
85  for (j=0; j<nnbrs; j++) {
86  if (pwgts[nbrind[j]] < maxpwgt) {
87  epart[i] = nbrind[j];
88  break;
89  }
90  }
91  if (j == nnbrs)
92  epart[i] = nbrind[iamax(nnbrs, nbrwgt)];
93  }
94  pwgts[epart[i]]++;
95  }
96  }
97 
98  if (*numflag == 1)
99  ChangeMesh2FNumbering2((*ne)*esize, elmnts, *ne, *nn, epart, npart);
100 
101  GKfree(&xadj, &adjncy, &pwgts, LTERM);
102 
103 }
104 
105 
106 /*************************************************************************
107 * This function partitions a finite element mesh by partitioning its dual
108 * graph using KMETIS and then assigning nodes in a load balanced fashion.
109 **************************************************************************/
110 void METIS_PartMeshDual(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag,
111  int *nparts, int *edgecut, idxtype *epart, idxtype *npart)
112 {
113  int i, j, k, me;
114  idxtype *xadj, *adjncy, *pwgts, *nptr, *nind;
115  int options[10], pnumflag=0, wgtflag=0;
116  int nnbrs, nbrind[200], nbrwgt[200], maxpwgt;
117  int esize, esizes[] = {-1, 3, 4, 8, 4};
118 
119  esize = esizes[*etype];
120 
121  if (*numflag == 1)
122  ChangeMesh2CNumbering((*ne)*esize, elmnts);
123 
124  xadj = idxmalloc(*ne+1, "METIS_MESHPARTNODAL: xadj");
125  adjncy = idxmalloc(esize*(*ne), "METIS_MESHPARTNODAL: adjncy");
126 
127  METIS_MeshToDual(ne, nn, elmnts, etype, &pnumflag, xadj, adjncy);
128 
129  options[0] = 0;
130  METIS_PartGraphKway(ne, xadj, adjncy, NULL, NULL, &wgtflag, &pnumflag, nparts, options, edgecut, epart);
131 
132  /* Construct the node-element list */
133  nptr = idxsmalloc(*nn+1, 0, "METIS_MESHPARTDUAL: nptr");
134  for (j=esize*(*ne), i=0; i<j; i++)
135  nptr[elmnts[i]]++;
136  MAKECSR(i, *nn, nptr);
137 
138  nind = idxmalloc(nptr[*nn], "METIS_MESHPARTDUAL: nind");
139  for (k=i=0; i<(*ne); i++) {
140  for (j=0; j<esize; j++, k++)
141  nind[nptr[elmnts[k]]++] = i;
142  }
143  for (i=(*nn); i>0; i--)
144  nptr[i] = nptr[i-1];
145  nptr[0] = 0;
146 
147 
148  /* OK, now compute a nodal partition based on the element partition npart */
149  idxset(*nn, -1, npart);
150  pwgts = idxsmalloc(*nparts, 0, "METIS_MESHPARTDUAL: pwgts");
151  for (i=0; i<*nn; i++) {
152  me = epart[nind[nptr[i]]];
153  for (j=nptr[i]+1; j<nptr[i+1]; j++) {
154  if (epart[nind[j]] != me)
155  break;
156  }
157  if (j == nptr[i+1]) {
158  npart[i] = me;
159  pwgts[me]++;
160  }
161  }
162 
163  maxpwgt = 1.03*(*nn)/(*nparts);
164  for (i=0; i<*nn; i++) {
165  if (npart[i] == -1) { /* Assign the boundary element */
166  nnbrs = 0;
167  for (j=nptr[i]; j<nptr[i+1]; j++) {
168  me = epart[nind[j]];
169  for (k=0; k<nnbrs; k++) {
170  if (nbrind[k] == me) {
171  nbrwgt[k]++;
172  break;
173  }
174  }
175  if (k == nnbrs) {
176  nbrind[nnbrs] = me;
177  nbrwgt[nnbrs++] = 1;
178  }
179  }
180  /* Try to assign it first to the domain with most things in common */
181  j = iamax(nnbrs, nbrwgt);
182  if (pwgts[nbrind[j]] < maxpwgt) {
183  npart[i] = nbrind[j];
184  }
185  else {
186  /* If that fails, assign it to a light domain */
187  npart[i] = nbrind[0];
188  for (j=0; j<nnbrs; j++) {
189  if (pwgts[nbrind[j]] < maxpwgt) {
190  npart[i] = nbrind[j];
191  break;
192  }
193  }
194  }
195  pwgts[npart[i]]++;
196  }
197  }
198 
199  if (*numflag == 1)
200  ChangeMesh2FNumbering2((*ne)*esize, elmnts, *ne, *nn, epart, npart);
201 
202  GKfree(&xadj, &adjncy, &pwgts, &nptr, &nind, LTERM);
203 
204 }
#define MAKECSR(i, n, a)
Definition: macros.h:91
void METIS_MeshToNodal(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag, idxtype *dxadj, idxtype *dadjncy)
Definition: mesh.c:42
#define LTERM
Definition: defs.h:18
void METIS_PartMeshDual(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag, int *nparts, int *edgecut, idxtype *epart, idxtype *npart)
Definition: meshpart.c:110
int idxtype
Definition: struct.h:19
#define iamax
Definition: rename.h:392
#define idxsmalloc
Definition: rename.h:386
#define ChangeMesh2FNumbering2
Definition: rename.h:68
#define idxset
Definition: rename.h:390
void METIS_PartGraphKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, idxtype *part)
Definition: kmetis.c:22
void GKfree(void **ptr1,...)
Definition: util.c:121
void METIS_MeshToDual(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag, idxtype *dxadj, idxtype *dadjncy)
Definition: mesh.c:23
void METIS_PartMeshNodal(int *ne, int *nn, idxtype *elmnts, int *etype, int *numflag, int *nparts, int *edgecut, idxtype *epart, idxtype *npart)
Definition: meshpart.c:22
#define idxmalloc
Definition: rename.h:383
#define ChangeMesh2CNumbering
Definition: rename.h:66