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 
42 
43  /* renumber the mesh */
44  if (renumber) {
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,
58  else
61 
62  if (rstatus != METIS_OK)
63  raise(SIGERR);
64 
65  /* partition the other side of the mesh */
67 
68 
69 SIGTHROW:
70  if (renumber) {
73  }
74 
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);
112 
113  /* renumber the mesh */
114  if (renumber) {
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,
128  else
129  rstatus = METIS_PartGraphRecursive(ne, &ncon, xadj, adjncy, vwgt, vsize, NULL,
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 */
154 
155  gk_free((void **)&nptr, &nind, LTERM);
156 
157 
158 SIGTHROW:
159  if (renumber) {
162  }
163 
164  METIS_Free(xadj);
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 }
ChangeMesh2FNumbering2
#define ChangeMesh2FNumbering2
Definition: rename.h:87
objval
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t * objval
Definition: include/metis.h:215
gk_sigtrap
int gk_sigtrap()
Definition: error.c:97
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
METIS_PartGraphRecursive
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
METIS_OPTION_PTYPE
@ METIS_OPTION_PTYPE
Definition: include/metis.h:271
gk_siguntrap
int gk_siguntrap()
Definition: error.c:115
metis_rcode
#define metis_rcode
Definition: rename.h:247
tpwgts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
Definition: include/metis.h:199
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
METIS_PartMeshNodal
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
imalloc
#define imalloc
Definition: gklib_rename.h:42
ncommon
idx_t idx_t idx_t idx_t * ncommon
Definition: include/metis.h:208
gk_sigcatch
#define gk_sigcatch()
Definition: gk_macros.h:52
npart
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t idx_t idx_t * npart
Definition: include/metis.h:215
METIS_PartGraphKway
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
ismalloc
#define ismalloc
Definition: gklib_rename.h:68
GETOPTION
#define GETOPTION(options, idx, defval)
Definition: metis/libmetis/macros.h:31
ncon
idx_t * ncon
Definition: include/metis.h:197
InduceRowPartFromColumnPart
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
nparts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
Definition: include/metis.h:199
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
METIS_OK
@ METIS_OK
Definition: include/metis.h:254
METIS_Free
int METIS_Free(void *ptr)
Definition: auxapi.c:23
LTERM
#define LTERM
Definition: gk_defs.h:14
eind
idx_t idx_t idx_t * eind
Definition: include/metis.h:207
SIGERR
#define SIGERR
Definition: gk_defs.h:38
METIS_PTYPE_KWAY
@ METIS_PTYPE_KWAY
Definition: include/metis.h:304
METIS_MeshToDual
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
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
eptr
idx_t idx_t * eptr
Definition: include/metis.h:207
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
SHIFTCSR
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
epart
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t idx_t * epart
Definition: include/metis.h:215
iset
#define iset
Definition: gklib_rename.h:67
METIS_OPTION_NUMBERING
@ METIS_OPTION_NUMBERING
Definition: include/metis.h:288
real_t
float real_t
Definition: include/metis.h:132
MAKECSR
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
iargmax
#define iargmax
Definition: gklib_rename.h:23
nn
idx_t * nn
Definition: include/metis.h:207
ChangeMesh2CNumbering
#define ChangeMesh2CNumbering
Definition: rename.h:85
METIS_ERROR_MEMORY
@ METIS_ERROR_MEMORY
Definition: include/metis.h:256
METIS_MeshToNodal
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
options
Definition: options.h:16
gk_malloc_cleanup
void gk_malloc_cleanup(int showstats)
Definition: memory.c:118
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
METIS_PartMeshDual
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
idx_t
int32_t idx_t
Definition: include/metis.h:101
gk_malloc_init
int gk_malloc_init()
Definition: memory.c:99


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:33:47