5 Mesh Ghosts

A ghost entity is a local, read-only copy of a real entity on another chunk. Ghosts are typically added to the boundary of a chunk to allow the real (non-ghost) elements at the boundary to access values across the processor boundary. This makes a chunk ``feel'' as if it was part of a complete unpartitioned mesh; and can be useful with cell-centered methods, and in mesh modification.

Figure 4: A small mesh partitioned into two pieces.
Figure 5: The same mesh with one layer of edge-adjacent ghosts.
Figure 6: The same mesh with one layer of node-adjacent ghosts.

In Figure 4, we begin with a small mesh partitioned into pieces on the left and right. In Figure 5, we have added ghost elements (dark hashing) that share an edge with adjacent real elements (light hatching). In Figure 6, we add ghost elements that share at least one node with adjacent real elements.

5.1 Ghost Numbering

Ghosts and real entities are stored by the framework in separate lists--to access the ghost entity type, add FEM_GHOST to the real entity's type. For example, FEM_GHOST+FEM_ELEM+1 lists the ghost elements for elType 1. To get the number of ghost nodes, you would call FEM_Mesh_get_length(mesh,FEM_GHOST+FEM_NODE).

Figure 7: Node indices used in the element connectivity array. There are $n$ real nodes and $m$ ghosts.

For real elements, the element connectivity always consists of real nodes. But for ghost elements, the adjacent nodes may be missing, or may themselves be ghosts. Thus ghost element connectivity lists may include the invalid value -1 (in C) or 0 (in Fortran) to indicate that the corresponding node is not present; or may include values less than this, which indicate the corresponding node is a ghost. In C, ghost node $i$ is indicated by the value $-2-i$, while in Fortran, ghost node $i$ is indicated by the value $-i$. This node indexing system is illustrated in Figure 7, This indexing system is bizarre, but it allows us to keep the real and ghost nodes clearly separate, while still allowing real and ghost nodes to be added in increasing order at both ends.

Since the C tests are complicated, in C we recommend using these macros:

• FEM_Is_ghost_index(i) returns true if $i$ represents a ghost node. In Fortran, use the test $i$ .lt. $0$

• FEM_From_ghost_index(i) returns the ghost node's index given its connectivity entry. In Fortran, use the expression $-i$.

• FEM_To_ghost_index(i) returns the connectivity entry for a given ghost node index. In Fortran, again use the expression $-i$.

For example, a quadrilateral ghost element that is adjacent to, respectively, two real nodes 23 and 17, the tenth local ghost node, and one not-present node might have a connectivity entry of 23,17,-11,-1 (in C) or 23,17,-10,0 (in Fortran).

Applications may wish to use some other numbering, such as by storing all the ghost nodes after all the real nodes. The code to extract and renumber the connectivity of some 3-node triangles stored in FEM_ELEM+2 would be:

/* C version */
  int nReal=FEM_Mesh_get_length(mesh,FEM_ELEM+2);
  int nGhost=FEM_Mesh_get_length(mesh,FEM_GHOST+FEM_ELEM+2);
  typedef int intTriplet[3];
  intTriplet *conn=new intTriplet[nReal+nGhost];
  /* Extract real triangles into conn[0..nReal-1] */
  FEM_Mesh_data(mesh,FEM_ELEM+2,FEM_CONN, &conn[0][0], 0,nReal, 3,FEM_INDEX_0);
  /* Extract ghost triangles into conn[nReal..nReal+nGhost-1] */
  FEM_Mesh_data(mesh,FEM_GHOST+FEM_ELEM+2,FEM_CONN, &conn[nReal][0], 0,nGhost, 3,FEM_INDEX_0);
  
  /* Renumber the ghost triangle connectivity */
  for (int t=nReal;t<nReal+nGhost;t++)
    for (int i=0;i<3;i++) {
      int in=conn[t][i]; /* uses FEM ghost node numbering */
      int out; /* uses application's ghost numbering */
      if (in==-1) {
        out=some_value_for_missing_nodes;
      } else if (FEM_Is_ghost_index(in)) {
        out=first_application_ghost+FEM_From_ghost_index(in);
      } else /*regular real node*/ {
        out=in;
      }
      conn[t][i]=out;
    }

! F90 version
  INTEGER, ALLOCATABLE :: conn(3,:)
  INTEGER :: nReal,nGhost,t,i,in,out
  nReal=FEM_Mesh_get_length(mesh,FEM_ELEM+2)
  nGhost=FEM_Mesh_get_length(mesh,FEM_GHOST+FEM_ELEM+2)
  ALLOCATE(conn(3,nReal+nGhost))
  ! Extract real triangles into conn[1..nReal]
  CALL FEM_Mesh_data(mesh,FEM_ELEM+2,FEM_CONN, conn, 1,nReal, 3,FEM_INDEX_1)
  ! Extract ghost triangles into conn[nReal+1..nReal+nGhost]
  CALL FEM_Mesh_data(mesh,FEM_GHOST+FEM_ELEM+2,FEM_CONN, conn(1,nReal+1), 1,nGhost, 3,FEM_INDEX_1)
  
  ! Renumber the ghost triangle connectivity
  DO t=nReal+1,nReal+nGhost
    DO i=1,3
      in=conn(i,t)
      IF (in .EQ. 0) out=some_value_for_missing_nodes
      IF (in .LT. 0) out=first_application_ghost-1+(-in)
      IF (in .GT. 0) out=in
      conn(i,t)=out
    END DO
  END DO
  
  

5.2 Setting up the ghost layer

The framework's ghost handling is element-centric. You specify which kinds of elements should be ghosts and how they connect by listing their faces before partitioning.

• 
  
  void FEM_Add_ghost_layer(int nodesPerFace,int doAddNodes);
  SUBROUTINE FEM_Add_ghost_layer(nodesPerFace,doAddNodes)
  INTEGER, INTENT(IN) :: nodesPerFace,doAddNodes
  This routine creates a new layer of ghosts around each FEM chunk. nodesPerFace is the number of shared nodes that together form a ``face''. doAddNodes specifies that you want ghost nodes around your ghost elements. If doAddNodes is 0, ghost elements will have invalid -1 (in C) or 0 (in Fortran) connectivity entries where there is no corresponding local node.

  A face is an unordered ``tuple'' of nodes, and is an abstract way to describe which ghosts your application needs--an element will be added to your chunk if it connects to at least one of your elements' faces. For example, if you have a 3D, tetrahedral element that require ghosts on all 4 of its sides, this is equivalent to requiring ghosts of every element that shares all 3 nodes of one of your triangular faces, so for you a face is a 3-node triangle. If you have a 2D shape and want edge-adjacency, for you a face is a 2-node edge. If you want node-adjacent ghosts, a face is a single node.

  Calling this routine several times creates several layers of ghost elements, and the different layers need not have the same parameters.

• 
  
  void FEM_Add_ghost_elem(int elType,int facesPerElem,const int *elem2face);
  SUBROUTINE FEM_Add_ghost_elem(elType,facesPerElem,elem2face)
  INTEGER, INTENT(IN) :: elType,facesPerElem
  INTEGER, INTENT(IN) :: elem2face(nodesPerFace,facesPerElem)
  

  This call is used to specify which type of element is to be added to the current ghost layer. facesPerElem and elem2face specify a mapping between each element and the surrounding faces. The elem2face table lists, for each face, the nodes of this element which form the face, specified as element-local numbers--indices into this element's connectivity entry. The elem2face table should have nodesPerFace*facesPerElem entries, and no entry should be greater than nodePerEl for that element type.

  Because all faces must take up the same space in the array, elem2face can include special indices-- -1 for C, 0 for Fortran--that indicate the corresponding face is actually shorter than usual. For example, if nodesPerFace for this layer is 4, for 4-node quadrilateral faces, you could set one entry in elem2face to -1 to specify this is a 3-node triangular face. Faces of different lengths will never match, so this is just a simple way to add ghosts from two kinds of faces at once.

The above two routines are always used together. For example, if your elements are 3-node triangles and you only require one shared node for inclusion in a single ghost layer, you would use:

   FEM_Add_ghost_layer(1,1); /* 1 node per face: node adjacency */
   const static int tri2node[]={0,1,2};
   FEM_Add_ghost_elem(0,3,tri2node); /* triangles are surrounded by 3 nodes */

If you require two shared nodes (a shared edge), the code will look like:

   FEM_Add_ghost_layer(2,1); /* 2 nodes per face: edge adjacency */
   const static int tri2edge[]={0,1,  1,2,  2,0};
   FEM_Add_ghost_elem(0,3,tri2edge); /*triangles are surrounded by 3 edges */

5.3 Symmetries and Ghosts-Geometric Layer

The FEM framework can create ghosts not only of things that are on other processors, but also for various problem symmetries, like mirror reflection, and various types of periodicities. The interface for these ghosts is simple--you ask for the symmetries to be created, then you will get extra ghosts along each symmetry boundary. The symmetry ghosts are updated properly during any communication, even if the symmetry ghosts are ghosts of real local elements from the same chunk.

Figure 8: Illustrating symmetry ghost elements.

Figure 8 shows a chunk of a mesh for a rectangular domain with horizontal linear translational periodicity--that is, the domain repeats horizontally. Symmetry ghosts lie along the left and right sides; ordinary cross-processor parallel ghosts lie along the top edge where this chunk joins up with the rest of the domain; and the external boundary along the bottom of the chunk has no ghosts.

void FEM_Add_linear_periodicity( int nFaces,int nPer, const int *facesA,const int *facesB, int nNodes,const double *nodeLocs );
SUBROUTINE FEM_Add_linear_periodicity(nFaces,nPer,facesA,facesB, nNodes,nodeLocs)
INTEGER, INTENT(IN) :: nFaces, nPer, nNodes
INTEGER, INTENT(IN) :: facesA(nPer,nFaces), facesB(nPer,nFaces)
double precision, INTENT(IN) :: nodeLocs(3,nNodes)

Make facesA and facesB match up under linear translation. Each face of facesA must match up with exactly one face of facesB, but both the faces and the nodes within a face can be permuted in any order--the order is recovered by matching 3d locations in the nodeLocs array.

This call can be repeated, for example if the domain is periodic along several directions. This call can only be issued from init().

void FEM_Sym_coordinates(int elTypeOrMinusOne,double *locs);
SUBROUTINE FEM_Sym_coordinates(elTypeOrZero,locs)
INTEGER, INTENT(IN) :: elTypeOrZero
double precision, intent(inout) :: locs(3,<number of items>)

This call adjusts the 3d locations listed in locs so they respect the symmetries of their corresponding item. If elTypeOrZero is an element type, the locations are adjusted to match with the corresponding element; if elTypeOrZero is zero, the locations are adjusted to match up with the corresponding node.

This call is needed because symmetry ghost nodes and elements initially have their original locations, which must be adjusted to respect the symmetry boundaries. Thus this call is needed both for initial location data (e.g., from FEM_Get_node_data) as well as any communicated location data (e.g., from FEM_Update_ghost_field).

This call can only be issued from driver().

5.4 Advanced Symmetries and Ghosts-Lower Layer

The geometric symmetry layer in the preceeding section is actually a thin wrapper around this lower, more difficult to use layer.

void FEM_Set_sym_nodes(const int *canon,const int *sym);
SUBROUTINE FEM_Set_sym_nodes(canon,sym)
INTEGER, INTENT(IN) :: canon(nNodes)
INTEGER, INTENT(IN) :: sym(nNodes)

This call describes all possible symmetries in an extremely terse format. It can only be called from init(). The ``canonicalization array'' canon maps nodes to their canonical representative--if canon($i$)=canon($j$), nodes $i$ and $j$ are images of each other under some symmetry. The sym array has bits set for each symmetry boundary passing through a node.

For example, a 2d domain with 6 elements A, B, C, D, E, and F and 12 nodes numbered 1-12 that is mirror-symmetric on the horizontal boundaries but periodic in the vertical boundaries would look like:

   D^'|  D^ |  E^ |  F^ |  F^`
   -  1  -  2  -  3  -  4  -
   A' |  A  |  B  |  C  |  C`
   -  5  -  6  -  7  -  8  -
   D' |  D  |  E  |  F  |  F`
   -  9  - 10  -  11 -  12 -
   Av'|  Av |  Bv |  Cv |  Cv`

  v indicates the value has been shifted down (bottom boundary),
  ^ indicates the value has been shifted up (top boundary),
  ' indicates the value has been copied from the left (right boundary),
  ` indicates the value has been copied from the right (left boundary).

If we mark the left border with 1, the top with 2, the right with 4, and the bottom with 8, this situation is indicated by topologically pasting the top row to the bottom row by setting their canon entries equal, and marking each node with its symmetries.

Node	canon	sym
1	1	3 (left + top)
2	2	2 (top)
3	3	2 (top)
4	4	6 (top + right)
5	5	1 (left)
6	6	0 (none)
7	7	0 (none)
8	8	4 (right)
9	1	9 (left+bottom)
10	2	8 (bottom)
11	3	8 (bottom)
12	4	12 (bottom+right)

void FEM_Get_sym(int elTypeOrMinusOne,int *destSym);
void FEM_Get_sym(elTypeOrZero,destSym);
INTEGER, INTENT(IN) :: elTypeOrMinusOne
INTEGER, INTENT(OUT) :: destSym(nItems)

This call extracts the list of symmetry conditions that apply to an item type. If elType is an element type, it returns the symmetry conditions that apply to that element type; if elType is -1 (zero for Fortran), it returns the symmetry conditions that apply to the nodes. Symmetry conditions are normally only nonzero for ghost nodes and elements.

Mirror symmetry conditions are not yet supported, nor are multiple layers of symmetry ghosts, but both should be easy to add without changing this interface.