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 13931 2013-03-29 16:48:48Z karypis $
12  *
13  */
14 
15 #include "metislib.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 **************************************************************************/
25 {
26  int sigrval=0, renumber=0, ptype;
28  idx_t ncon=1, pnumflag=0;
29  int rstatus=METIS_OK;
30 
31  /* set up malloc cleaning code and signal catchers */
32  if (!gk_malloc_init())
33  return METIS_ERROR_MEMORY;
34 
35  gk_sigtrap();
36 
37  if ((sigrval = gk_sigcatch()) != 0)
38  goto SIGTHROW;
39 
40  renumber = GETOPTION(options, METIS_OPTION_NUMBERING, 0);
42 
43  /* renumber the mesh */
44  if (renumber) {
45  ChangeMesh2CNumbering(*ne, eptr, eind);
46  options[METIS_OPTION_NUMBERING] = 0;
47  }
48 
49  /* get the nodal graph */
50  rstatus = METIS_MeshToNodal(ne, nn, eptr, eind, &pnumflag, &xadj, &adjncy);
51  if (rstatus != METIS_OK)
52  raise(SIGERR);
53 
54  /* partition the graph */
55  if (ptype == METIS_PTYPE_KWAY)
56  rstatus = METIS_PartGraphKway(nn, &ncon, xadj, adjncy, vwgt, vsize, NULL,
57  nparts, tpwgts, NULL, options, objval, npart);
58  else
59  rstatus = METIS_PartGraphRecursive(nn, &ncon, xadj, adjncy, vwgt, vsize, NULL,
60  nparts, tpwgts, NULL, options, objval, npart);
61 
62  if (rstatus != METIS_OK)
63  raise(SIGERR);
64 
65  /* partition the other side of the mesh */
66  InduceRowPartFromColumnPart(*ne, eptr, eind, epart, npart, *nparts, tpwgts);
67 
68 
69 SIGTHROW:
70  if (renumber) {
71  ChangeMesh2FNumbering2(*ne, *nn, eptr, eind, epart, npart);
72  options[METIS_OPTION_NUMBERING] = 1;
73  }
74 
75  METIS_Free(xadj);
76  METIS_Free(adjncy);
77 
78  gk_siguntrap();
80 
81  return metis_rcode(sigrval);
82 }
83 
84 
85 
86 /*************************************************************************
87 * This function partitions a finite element mesh by partitioning its dual
88 * graph using KMETIS and then assigning nodes in a load balanced fashion.
89 **************************************************************************/
93  idx_t *npart)
94 {
95  int sigrval=0, renumber=0, ptype;
96  idx_t i, j;
97  idx_t *xadj=NULL, *adjncy=NULL, *nptr=NULL, *nind=NULL;
98  idx_t ncon=1, pnumflag=0;
99  int rstatus = METIS_OK;
100 
101  /* set up malloc cleaning code and signal catchers */
102  if (!gk_malloc_init())
103  return METIS_ERROR_MEMORY;
104 
105  gk_sigtrap();
106 
107  if ((sigrval = gk_sigcatch()) != 0)
108  goto SIGTHROW;
109 
110  renumber = GETOPTION(options, METIS_OPTION_NUMBERING, 0);
111  ptype = GETOPTION(options, METIS_OPTION_PTYPE, METIS_PTYPE_KWAY);
112 
113  /* renumber the mesh */
114  if (renumber) {
115  ChangeMesh2CNumbering(*ne, eptr, eind);
116  options[METIS_OPTION_NUMBERING] = 0;
117  }
118 
119  /* get the dual graph */
120  rstatus = METIS_MeshToDual(ne, nn, eptr, eind, ncommon, &pnumflag, &xadj, &adjncy);
121  if (rstatus != METIS_OK)
122  raise(SIGERR);
123 
124  /* partition the graph */
125  if (ptype == METIS_PTYPE_KWAY)
126  rstatus = METIS_PartGraphKway(ne, &ncon, xadj, adjncy, vwgt, vsize, NULL,
127  nparts, tpwgts, NULL, options, objval, epart);
128  else
129  rstatus = METIS_PartGraphRecursive(ne, &ncon, xadj, adjncy, vwgt, vsize, NULL,
130  nparts, tpwgts, NULL, options, objval, epart);
131 
132  if (rstatus != METIS_OK)
133  raise(SIGERR);
134 
135 
136  /* construct the node-element list */
137  nptr = ismalloc(*nn+1, 0, "METIS_PartMeshDual: nptr");
138  nind = imalloc(eptr[*ne], "METIS_PartMeshDual: nind");
139 
140  for (i=0; i<*ne; i++) {
141  for (j=eptr[i]; j<eptr[i+1]; j++)
142  nptr[eind[j]]++;
143  }
144  MAKECSR(i, *nn, nptr);
145 
146  for (i=0; i<*ne; i++) {
147  for (j=eptr[i]; j<eptr[i+1]; j++)
148  nind[nptr[eind[j]]++] = i;
149  }
150  SHIFTCSR(i, *nn, nptr);
151 
152  /* partition the other side of the mesh */
153  InduceRowPartFromColumnPart(*nn, nptr, nind, npart, epart, *nparts, tpwgts);
154 
155  gk_free((void **)&nptr, &nind, LTERM);
156 
157 
158 SIGTHROW:
159  if (renumber) {
160  ChangeMesh2FNumbering2(*ne, *nn, eptr, eind, epart, npart);
161  options[METIS_OPTION_NUMBERING] = 1;
162  }
163 
164  METIS_Free(xadj);
165  METIS_Free(adjncy);
166 
167  gk_siguntrap();
169 
170  return metis_rcode(sigrval);
171 }
172 
173 
174 
175 /*************************************************************************/
178 /*************************************************************************/
179 void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind,
180  idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts)
181 {
182  idx_t i, j, k, me;
183  idx_t nnbrs, *pwgts, *nbrdom, *nbrwgt, *nbrmrk;
184  idx_t *itpwgts;
185 
186  pwgts = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: pwgts");
187  nbrdom = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: nbrdom");
188  nbrwgt = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: nbrwgt");
189  nbrmrk = ismalloc(nparts, -1, "InduceRowPartFromColumnPart: nbrmrk");
190 
191  iset(nrows, -1, rpart);
192 
193  /* setup the integer target partition weights */
194  itpwgts = imalloc(nparts, "InduceRowPartFromColumnPart: itpwgts");
195  if (tpwgts == NULL) {
196  iset(nparts, 1+nrows/nparts, itpwgts);
197  }
198  else {
199  for (i=0; i<nparts; i++)
200  itpwgts[i] = 1+nrows*tpwgts[i];
201  }
202 
203  /* first assign the rows consisting only of columns that belong to
204  a single partition. Assign rows that are empty to -2 (un-assigned) */
205  for (i=0; i<nrows; i++) {
206  if (rowptr[i+1]-rowptr[i] == 0) {
207  rpart[i] = -2;
208  continue;
209  }
210 
211  me = cpart[rowind[rowptr[i]]];
212  for (j=rowptr[i]+1; j<rowptr[i+1]; j++) {
213  if (cpart[rowind[j]] != me)
214  break;
215  }
216  if (j == rowptr[i+1]) {
217  rpart[i] = me;
218  pwgts[me]++;
219  }
220  }
221 
222  /* next assign the rows consisting of columns belonging to multiple
223  partitions in a balanced way */
224  for (i=0; i<nrows; i++) {
225  if (rpart[i] == -1) {
226  for (nnbrs=0, j=rowptr[i]; j<rowptr[i+1]; j++) {
227  me = cpart[rowind[j]];
228  if (nbrmrk[me] == -1) {
229  nbrdom[nnbrs] = me;
230  nbrwgt[nnbrs] = 1;
231  nbrmrk[me] = nnbrs++;
232  }
233  else {
234  nbrwgt[nbrmrk[me]]++;
235  }
236  }
237  ASSERT(nnbrs > 0);
238 
239  /* assign it first to the domain with most things in common */
240  rpart[i] = nbrdom[iargmax(nnbrs, nbrwgt)];
241 
242  /* if overweight, assign it to the light domain */
243  if (pwgts[rpart[i]] > itpwgts[rpart[i]]) {
244  for (j=0; j<nnbrs; j++) {
245  if (pwgts[nbrdom[j]] < itpwgts[nbrdom[j]] ||
246  pwgts[nbrdom[j]]-itpwgts[nbrdom[j]] < pwgts[rpart[i]]-itpwgts[rpart[i]]) {
247  rpart[i] = nbrdom[j];
248  break;
249  }
250  }
251  }
252  pwgts[rpart[i]]++;
253 
254  /* reset nbrmrk array */
255  for (j=0; j<nnbrs; j++)
256  nbrmrk[nbrdom[j]] = -1;
257  }
258  }
259 
260  gk_free((void **)&pwgts, &nbrdom, &nbrwgt, &nbrmrk, &itpwgts, LTERM);
261 
262 }
idx_t idx_t idx_t idx_t * vwgt
int gk_siguntrap()
Definition: error.c:116
idx_t idx_t idx_t idx_t * ncommon
int METIS_Free(void *ptr)
Definition: auxapi.c:23
#define imalloc
Definition: gklib_rename.h:42
#define ismalloc
Definition: gklib_rename.h:68
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
#define metis_rcode
Definition: rename.h:247
idx_t idx_t * xadj
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t idx_t * epart
idx_t idx_t * eptr
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
#define iargmax
Definition: gklib_rename.h:23
idx_t idx_t idx_t idx_t idx_t * vsize
idx_t idx_t idx_t * eind
#define ASSERT(expression)
Definition: ccolamd.c:872
int METIS_PartMeshDual(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, idx_t *vwgt, idx_t *vsize, idx_t *ncommon, idx_t *nparts, real_t *tpwgts, idx_t *options, idx_t *objval, idx_t *epart, idx_t *npart)
Definition: meshpart.c:90
int METIS_PartMeshNodal(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, idx_t *vwgt, idx_t *vsize, idx_t *nparts, real_t *tpwgts, idx_t *options, idx_t *objval, idx_t *epart, idx_t *npart)
Definition: meshpart.c:22
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t * objval
#define ChangeMesh2FNumbering2
Definition: rename.h:87
#define SIGERR
Definition: gk_defs.h:38
int32_t idx_t
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t idx_t idx_t * npart
void gk_malloc_cleanup(int showstats)
Definition: memory.c:118
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
int METIS_MeshToNodal(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, idx_t *numflag, idx_t **r_xadj, idx_t **r_adjncy)
Definition: mesh.c:114
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
idx_t * nn
#define iset
Definition: gklib_rename.h:67
void gk_free(void **ptr1,...)
Definition: memory.c:202
void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind, idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts)
Definition: meshpart.c:179
#define gk_sigcatch()
Definition: gk_macros.h:52
int METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval, idx_t *part)
Definition: kmetis.c:18
idx_t idx_t idx_t * adjncy
int METIS_PartGraphRecursive(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval, idx_t *part)
Recursive partitioning routine.
Definition: pmetis.c:91
int METIS_MeshToDual(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, idx_t *ncommon, idx_t *numflag, idx_t **r_xadj, idx_t **r_adjncy)
Definition: mesh.c:44
int gk_malloc_init()
Definition: memory.c:99
#define ChangeMesh2CNumbering
Definition: rename.h:85
std::ptrdiff_t j
int gk_sigtrap()
Definition: error.c:98
#define GETOPTION(options, idx, defval)
#define LTERM
Definition: gk_defs.h:14


gtsam
Author(s):
autogenerated on Sat May 8 2021 02:42:59