Data structures for storing the mesh

For a single-level finite element implementation, one only needs to have data structures for elements and vertices. However, this is not suitable for a multilevel solver since additional operations such as subdividing the mesh must be performed and traversing the multilevel tree to assemble the stiffness matrix must be done efficiently. To efficiently store and retrive the geometry, we used a Vertex-Edge-Element datastructure which is described below:

1. Vertex. Each vertex stores its coordinates and a flag to indicate whether it is restrained or not.
2. Edge. Each edge stores the IDs of its bounding vertices and the ID of its two children edges. It also contains a flag to indicate whether it is restrained or not.
3. Element. Each element/face contains a list of four of its bounding edges along with the ID of the face vertex created during subdivision.

Note that we need to store the boundary conditions for nodes and edges since they both influence the boundary conditions for internal edges and nodes created during subdivision. The vertex, edge and element data structures are implemented using arrays of C structs. To reduce runtime overhead, member access is provided using macros rather than functions. In addition to the mesh datastructures , a seperate data structure keeps track of the starting end ending edges and elements at a given level of subdivision. In designing the above data structures, we have tried to strike a balance between the memory requirement, the cost of accessing the various topological elements and ease of implementation. In particular, our multilevel datastructure has be implemented using arrays as opposed to linked-lists or quad-trees, which have significantly larger memory requirements. Moreover, the topological entities of interest can be accessed in constant time. For example, all the bounding vertices of an element can be determined using only eight memory references and all its child vertices can be accessed using only 12 memory references.