Metis for finite element triangular mesh partitioning

[Cplusc]

I am trying to use Metis to partition a finite element mesh. however, In the metis manual I read something that made me feel confused a little.

"All of the mesh partitioning and mesh conversion routines in METIS take as input the element node array of a mesh. This element node array is stored using a pair of arrays called eptr and eind, which are similar to the xadj and adjncy arrays used for storing the adjacency structure of a graph. The size of the eptr array is n+ 1, where n is the number of elements in the mesh. The size of the eind array is of size equal to the sum of the number of nodes in all the elements of the mesh. The list of nodes belonging to the ith element of the mesh are stored in consecutive locationsof eind starting at position eptr[i] up to (but not including) position eptr[i+1]."

I wonder if the size of eptr shouldn't be of size node +1?

and for partitioning I am using

METIS_PartMeshNodal(&ne, &nn, &eptr, &eind, NULL, NULL, &nparts, NULL, NULL, &objval, &epart, &npart);

but I don't know how to send different part to different processors. any help would be appreciated.

[ne555]

if i read correctly
eind have repeated nodes, for example if you have two triangular elements, you'll store six nodes, doesn't matter if they share or not a vertex or edge.
that way eptr[k] holds pointers to the "array" of nodes of element k, that are stored in eind

for example, a triangular element k, will have its nodes on {eptr[k][0], eptr[k][1], eptr[k][2]}
and it would hold that eptr[k+1] - eptr[k] == 3

so size eptr is elements + 1

edit: I thought that eptr stored pointers, if it stores indices instead, then the nodes would be on
{eind[eptr[k]], eind[eptr[k]+1], eind[eptr[k]+2]}


> but I don't know how to send different part to different processors.
I don't know if the repeated nodes may cause you issues
also, I guess that you need to reorder eind to have geometric regions stored consecutively
¿what are the parameters for METIS_PartMeshNodal?


ps: the manual http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/manual.pdf

[Cplusc]

Thanks for your answer.

for example, a triangular element k, will have its nodes on {eptr[k][0], eptr[k][1], eptr[k][2]}

so is it the connectivity matrix?I feel that the way you described the eptr, eptr can be achieved by pushing ack the connectivity into an 1D array. and in that case the size will not be n+1 if i'm not mistaken.

the parameter is
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);

ne number of element, nn number of node, npart the number if intended devision which in my case will be the number of processors, vwgt is the wight of vertices being NULL in my case. tpwgts, option,objval are NULL as well in my case.

[ne555]

> eptr can be achieved by pushing ack the connectivity into an 1D array.
not sure what you are trying to say, ¿may provide an example?

I'l suggest you to create some simple meshes ((a) one triangle, (b) two separate elements, (c) two triangles sharing an edge) and observe the content of the arrays


> but I don't know how to send different part to different processors
I don't know what kind of interface you have to communicate with the processors
with the epart array you may obtain the elements that form part of the 'x' partition, ¿but then what? ¿do you need to store all those elements in another array so you pass a contiguous chunk?
¿and what do you do with the edges between partitions?

never worked with that library, can't help you further, try an specific forum

regards

[Cplusc]

Thanks for you answer. I have a mesh which consists a number of elements. Right now, I'm just dividing my element into several part and sending them to different processors without any consideration. Then each processor is responsible for constructing the sparse matrices required for the finite element. Now I want to send the chunk of elements to each processor. All processors will be having the coordinate of all nodes but just a chunk of element. For this I'm using metispartmeshnodal I I am confused with eptr and eind.
Imagine this is my connectivity

Elements
1 11 13 7
2 15 12 9
3 9 12 6
4 15 9 14
5 2 1 3
6 14 16 15
7 10 6 12
8 3 7 5
9 5 7 8
10 3 4 2
11 13 14 8
12 8 14 9
13 13 8 7
14 6 2 4
15 4 3 5
16 6 4 9
17 8 9 4
18 5 8 4
End Elements
Now I want metis give me the chunk of element for each processor. What is the eptr and iend?
As I understand from your answer eptr is a one dimensional vector obtained by pushing back the connectivity. And iend is 0,3,6,9....?

[ne555]

backwards
eptr = {0, 3, 6, 9, ..., 3*18}; size 19 (elements + 1)
eind = {11, 13, 7, 15, 12, 9, ..., 5, 8, 4}; size 3*18 (sum of all the nodes in all the elements)

> All processors will be having the coordinate of all nodes but just a chunk of element.

4.2.1 Partition file
The partition file of a graph with n vertices consists of n lines with a single number per line. The ith line of the file contains the partition number that the ith vertex belongs to. Partition numbers start from 0 up to the number of partitions minus one.

epart
This is a vector of size ne (number of elements) that upon successful completion stores the partition vector for the elements of the mesh.

for j in [0, n_partitions):
  chunk = elements[epart = j] #select the elements that are in partition j
  # send chunk of elements 

[Cplusc]

When I obtain eptr and eind according to what we have discussed here so far, i get this bug after running the code. "dividision of integer by zero". I tried for another routine of metis partgraphkway with the adjancy matrices and the same happened there. I don't understand why this is happening? Can it cause because of the precision definition inside the metis?