1.2 Terminology

A FEM program manipulates elements and nodes. An element is a portion of the problem domain, also known as a cell, and is typically some simple shape like a triangle, square, or hexagon in 2D; or tetrahedron or rectangular solid in 3D. A node is a point in the domain, and is often the vertex of several elements. Together, the elements and nodes form a mesh, which is the central data structure in the FEM framework.

An element knows which nodes surround it via the element's connectivity table, which lists the nodes adjacent to each element.

Figure 1: 3-element, 5 node mesh.

Table 1: Connectivity table for mesh in figure 1.

Element	Adjacent Nodes
e1	n1	n3	n4
e2	n1	n2	n4
e3	n2	n4	n5

A typical FEM program performs some element-by-element calculations which update adjacent node values; then some node-by-node calculations. For example, a material dynamics program has the structure:

     time loop
          element loop- Element deformation applies forces to
          surrounding nodes
          node loop- Forces and boundary conditions change node
          positions
     end time loop

We can parallelize such FEM programs by partitioning the serial mesh elements into several smaller meshes, or chunks. There is normally at least one chunk per processor; and often even more. During partitioning, we give nodes and elements new, local numbers within that chunk. In the figure below, we have partitioned the mesh above into two chunks, A and B.

Figure 2: Partitioned mesh.

Table 2: Connectivity table for chunk A in figure 2.

Element	Adjacent Nodes
e1	n1	n3	n4
e2	n1	n2	n4

Table 3: Connectivity table for chunk B in figure 2.

Element	Adjacent Nodes
e1	n1	n2	n3

Note that chunk A's node n2 and B's node n1 were actually the same node in the original mesh- partitioning split this single node into two shared copies (one on each chunk). However, since adding forces is associative, we can handle shared nodes by computing the forces normally (ignoring the existence of the other chunk), then adding both chunks' net force for the shared node together. This ``node update'' will give us the same resulting force on each shared node as we would get without partitioning, thus the same positions, thus the same final result.

For example, under hydrostatic pressure, each chunk might compute a local net force vector for its nodes as shown in Figure 3 (a). After adding forces across chunks, we have the consistent global forces shown in Figure 3 (b).

Figure 3: A force calculation decomposed across chunks: (a) before update (b) after updating forces across nodes.

Hence, each chunk's time loop has the structure:

     chunk time loop
          element loop- Element deformation applies forces to
          surrounding nodes
          <update forces on shared nodes>
          node loop- Forces and boundary conditions change node
          positions
     end time loop

This is exactly the form of the time loop for a CHARM++ FEM framework program. The framework will accept a serial mesh, partition it, distribute the chunks to each processor, then you run your time loop to perform analysis and communication.