In Search for the Super Element: Algorithms to Generate Higher Order Elements

This work was motivated by the need that may arise during the creation of finite element programs, for higher order elements. The problem of selecting or creating shape functions that satisfy the required need of the problem may be one major problem that stand in the way of the element creation. In this work we present an attempt that points in the direction of creating the element matrices for higher order elements using simple, Lagrange, and modified Lagrange polynomials. The results obtained for the test cases indicate the possibilities and limitations on those attempts. It is concluded that the modifies Lagrange polynomials have a great potential for use in elements with high number of nodes and/or high number of DOF per node. Nevertheless, they impose a high computational cost on the element matrices generation.


INTRODUCTION
In the past decades, the finite element method has grown into a well developed numerical technique that can be used to provide accurate and relatively quick solution to boundary value problems that describe several physical problems. The procedure of the finite element model starts by dividing the domain into elements that are connected through nodes. Each node has degrees of freedom (DOF) that, usually, present the value and derivatives of the physical function of interest. Then the elements are defined by the interpolation functions that describe the change of the function within their boundaries. Following that, the whole domain description is created by assembling the elements and applying the boundary conditions. Finally, the problem is solved to obtain the values of the DOF of all the nodes. 1,2 The basic assumption is that as the number of elements increase in the domain, the solution approaches the exact one. The power of the finite element method lies in that it may use simple functions, usually polynomials, to describe the change of the target function inside an element, and then use that to describe the change in the whole domain by assembling the different elements that cover the domain.
Another approach to reach higher accuracy is to increase the order of each of the elements used in the model which reduces the need for higher number of elements (p-version finite element). Higher order elements may be generated by using more nodes in the element, using more complex functions, or by hierarchical elements. 3,4,5,6 Most of the work performed for the solution of the finite element problem is algorithmic, that enabled the excessive use computers and the production of computer packages that can manipulate several physical problems with complex domain geometries. Nevertheless, in the core of all finite element codes, lies the element matrices. The element matrices are generated through the knowledge of the mathematical model that describes the physical problem and the selection of the interpolation functions, shape functions. Equipped with those two pieces of information, you may generate the element matrices for any physical problem. However, the generation of a general element is still far from algorithmic. 7 A special problem faces the generation of the finite element model is the selection of the interpolation function that satisfies the prescribed degrees of freedom at the nodes 5 When the DOF involve derivatives of the function, the Lagrange polynomials should be selected to satisfy the condition that they have the slope of one at the associated node and zero at the others as well. However, it is quite difficult to find the Lagrange polynomials that may be used in a general problem that is why they may be generated by using classical interpolation techniques.
The classical interpolation techniques require the evaluation of the polynomial coefficients by forcing the polynomial to satisfy the boundary conditions, thus, requiring the solution of a set algebraic equation, hence, the inversion of a matrix. The matrix inversion process is a straight forward numerical technique; however, as the number of variables increase, the matrix eventually becomes singular because of the round-off errors. 9, 10 Another challenge that faces the creators of finite element models is the performance of integration. The element matrices are generated by integrating the shape functions or their derivatives over the element. In many simple cases, the integration is readily available by hand or using symbolic manipulators. However, in more practical cases, numerical integration is required which, in turn, introduces errors to the resulting element models.
In the past years, several research articles were published, mostly by mathematics oriented researchers, about the topic of generating higher order polynomials, shape functions, for applications in the finite element models 5, 6, 8, 11, 12. Such research, among many others not cited here, accomplished a great task in the direction of generalizing the automation of finite element model generation.
Following that, an excellent attempt for the automation was presented in 7 using the symbolic manipulator Mathematica® and an accompanying package AceGen®.
None of the research reviewed by the author presented a straight-forward methodology that may be used by the engineers who need to create finite element models on numerical manipulators, thus, in the following work, we will be attempting to describe a generalize procedure for the generation of the finite element matrices with an eye on elements with large numbers of nodes and degrees of freedom. We will start by describing a classical method of generating the matrices and creating the shape functions, then we will move towards describing attempts to generate a general method for performing exact integration for generating element matrices. Following that, we will describe the attempts using Lagrange polynomials to avoid matrix inversion, finally, modifies Lagrange polynomials will be created to enable to the creation of different finite element problems.
The main purpose of this work is providing a methodology that may by applied using numerical manipulators, especially open source, to generate the element matrices that may be used by researchers without the need for commercial packages or commercial symbolic manipulators.

CLASSICAL APPROACH 2.1. Interpolation Polynomials -Shape Functions
The finite element model starts by assuming the solution of the unknown function in terms of an interpolation polynomial that satisfies the values of the degrees of freedom at the nodes of the element. In most text, these functions are denoted the letter N such that: Where fi are the values of the function at node i and Ni(x) are polynomials that have the value of one at the corresponding node and zero at every other node. The above relation may be written as: The first problem that faces the researcher who wants to create a new finite element model is to find and select the polynomials that may be used for the problem. However, that is not a great problem for low order elements since the polynomials are readily available in many texts. Nevertheless, coding them may involve mistyping which will require debugging of the code. On the other hand, it becomes a bit inconvenient to change the number of nodes per element to test the effect of higher, or lower, order elements. Thus we may use another way of defining the polynomials that can reduce both problems, that is by using regular simple polynomials such that: Where ai are constants, generalized coordinates that should be determined for the function to satisfy the given values. To do that we will need to set a number of equations and solve them to find those values, thus: Which may be written as: {δ } It can be readily proven that: Thus using this procedure we were able to obtain the polynomials for any number of degrees of freedom without having to look them up in literature or enduring the problems of mistyping them into the code. However, nothing comes for free; using this method will involve matrix inversion which will become ill-conditioned as the number of degrees of freedom increase.
If the degrees of freedom of the element involve the derivatives of the function, we may adjust the above procedure. Given the value of the function fi and the fist derivative f'i, for example, we may write: Then the [T] matrix may be constructed such that: In this case, the number of degrees of freedom per element will be equal to twice the number of nodes and the function Ni(x) will appear in pairs. The first function of the pair will have a value of one at its corresponding node while the slope at that node is zero, and has a value and slope of zero at every other node. Meanwhile, the second function of the pair will have a slope of one and a value of zero at the corresponding node while its value and slope are equal to zero at every other node.
Note that, in both cases above, the order of the polynomial terms in the H(x) matrix does not affect the resulting shape functions because they are going to be rearranged using the T matrix.

Element Matrices
Each finite element problem will generate a set of matrices for each element. These matrices are derived from the physical model that is usually presented in the form of a differential equation. The matrices are constructed by integrating some derivative of the function that usually appears in the form: Where Q(x) is some function that describes the physical properties of the problem, D m (.) is a differential operator that differentiates the function f(x) m times. For example, in mechanics of material, the finite element matrix for a bar in static problem may be obtained using: Where E(x) and A(x) are the modulus of elasticity and the cross-section area respectively. For simple problems, the above integral may be performed by hand or using symbolic manipulators. However, it is more convenient to use numerical integration in order to add flexibility to the programming. Nevertheless, some cases will not allow for hand or symbolic manipulators' integration, thus it is common to find numerical integration routines associated with any finite element program. One of the popular techniques used for numerical integration is the Gauss-Legendre quadrature which produces almost exact integration for polynomials that may reach up to 24 th order. 12

2-D Problems
In 2-D problems, the interpolation polynomials should include combinations of the x and y coordinates. To identify the terms, the common practice is to select them from what is known as the Pascal triangle (See Figure 1). The number of terms selected should be equal to the number of degrees of freedom and it is recommended that the terms should create a symmetric shape in that triangle.

Figure 1. Pascal triangle
The Pascal triangle is quite handy in many problems, however, if you strict your work to using the full polynomials in both directions, then the generation of the terms becomes quite straight forward by multiplying both x and y-polynomials. For example, for a quadrilateral element with a single degree of freedom per node, we need a linear polynomial in each of the directions, hence, we may write: →H ( x, y)= ⌊1 x y xy ⌋ Then we proceed with the H(x,y) vector just as in the 1-D cases: Note, again, that the order of the polynomial terms in the H vector will not affect the resulting shape functions similar to what we had in the 1-D problems. At this point, we still have both problems when generating the higher order elements, namely, the matrix inversion and the numerical integration. In the following section, we will attempt generating the matrices using exact integration to avoid the numerical integration problem.

EXACT INTEGRATION
To avoid the errors introduced by the numerical integration, we may resolve to exact integration using symbolic manipulators (wxMaxima® , Mathematica® , Mable® , etc …) but then we are back to the problem of rewriting the element matrices into our code, with all the problems that may include, or write the whole finite element model using the symbolic package which is normally extremely slow when it comes to numerical manipulations compare to numerical coding packages (Octave® , Matlab® , etc ...) or programming languages (Fortran, C++, etc …). Thus, we resolve to write an algorithm to perform the exact integration on the numerical package for specific elements with unknown number of degrees of freedom. This is where the H(x) row-matrix becomes very handy. Since the row-matrix is composed of simple polynomial terms, their differentiation, and later integration, is readily evaluated.
Let's examine the case of a bar element with n nodes (and n degrees of freedom). For the bar element, the element matrix, stiffness matrix, is evaluated using the integration: For the sake of the illustration, we will assume that the modulus of elasticity and the cross-section area are constants, thus, we may write: But, the transformation matrix is also constant, thus, it may be dragged out of the integration leaving us with the derivative of the H(x) vector.
In this case, the T matrix may be given as: If we examine the terms of the H(x) vector, we may write: Thus the first derivative may be written as: International Journal of Trend in Scientific Research and Development (IJTSRD) ISSN: 2456-6470 Page: 512 Hence, we may write the matrix: From that, we may get the integration: Similarly, for any 1-D problem involving any derivative, we may readily obtain the general term for the G matrix and perform the integration to obtain the G* matrix.
Let's examine the case of a beam element with n nodes (and 2n degrees of freedom). For the beam element, the element matrix, stiffness matrix, is evaluated using the integration: For the sake of the illustration, we will assume that the modulus of elasticity and the cross-section second moments of area are constants, thus, we may write: But, the transformation matrix is also constant, thus, it may be dragged out of the integration leaving us with the derivative of the H(x) vector.
In this case, the T matrix may be given as: If we examine the terms of the H(x) vector, we may write: Thus the second derivative may be written as: From that, we may get the integration:

, n
For 2-D problems, the problem becomes a little more complex. The general term of the H(x,y) vector will depend on the order at which we select the terms from the Pascal's triangle. For illustration, let's assume that we are going to generate a rectangular element for plate bending that ensures continuity of slope (C 1 element).
In this case, the number of nodes in the element may be selected to be n 2 where n is the number of nodes per side of the element (n=2,3,4, …) in this case the number of degrees of freedom per element will be 4n 2 , and the x and y polynomials, each, will be of 2n-1 order. We may write:

,2n
And the derivatives of the H vector, may be written as: The element stiffness matrix for the static loading problem of thin plates may be written as: Where: And: Whose general term may be written as: [Q] is the plate stiffness which may be written, for the sake of compactness, in the form: The matrix [G] may be written as: where the general term may evaluated by: Similarly: From which, we may get the integral of the general term of the [G] matrix in the form: a(α 1 +α 4 )+b(α 2 +α 3 )+4Cα 5 In both the 1-D and 2-D problems illustrated above, we were able to create the element matrices exactly using the trick of integrating the H vector and its derivatives. However, the limiting condition on generating high order elements will always be the inversion of the T matrix which will become ill-conditioned with higher order elements. For example, the plate bending element described above worked only until the number of nodes became 16 (64 DOF) (7 th order polynomial in each of the x and y directions) using double precision numbers on the Octave numerical manipulator. Hence, a search for another technique was required.

LAGRANGE POLYNOMIALS 4.1. 1-D problems
The Lagrange interpolation polynomial for an (n-1) th order polynomial, which may be used when n degrees of freedom are give, may be written in the form: Thus, we may obtain the first derivative in the form: We may also obtain further derivatives for use in the element equation, however, let's remember that the function interpolation is based on the values of the function, thus, if we need to have any of the derivatives of the function as a degree of freedom, we cannot use this interpolation method. Nevertheless, we have obtained the shape functions without having to go through the matrix inversion problem described in the previous section. On the other hand, performing the exact integration will not be readily available for the general term since it now involves multiplication of several linear terms. Luckily, as mentioned earlier, the Gauss quadrature integration provides high degree of accuracy for a relatively high order polynomial integration.
Note that he order of the Lagrange polynomials used above has to coincide with the order of the node numbering unlike the cases we described in sections 2 and 3 above.

2-D Problems
With the same advantages and disadvantages of the 1-D problem, the derivation of the shape functions for a 2-D problem comes straight forward by multiplying the polynomials in the x and y directions.
In a vector, we usually use a single index to point to the different element, thus, we need to create a relation between the vector index and the i and j counters of the nodes counters in a 2-D element. A simple relation for counting the nodes in the x-direction first would be in the form: Thus we may write the general shape function in the form: For which we may evaluate the first derivatives to be:

MODIFYING THE INTERPOLATION FUNCTION
Borrowing from the Spline interpolation techniques, we may work around with the Lagrange polynomials to obtain polynomials that may include derivatives of the function. In the following, we will work with functions that are required to satisfy the value of the function and its first derivative at each node of the element. We will start be deriving the cubic polynomial that will fit 2 values and two slopes, then, we will describe the process for quintic polynomial, followed by the general approach for obtaining the (2n-1) th polynomial that may be used for n-node elements.

The Polynomials
Using the similarities we obtained in the 3 rd and 5 th order polynomial derivation, we will present a generalization in the following section. We may write the general relation for a function of the (2n-1) th order that uses n pairs of polynomials as: Where: This function needs to satisfy the conditions: For the first condition, we get: To proceed with the second condition, we get the slopes as: Substituting: Which gives: Thus we may write the pair of polynomials as: Rearranging, we obtain: From which we may write the shape functions as: In 2-D problems, the interpolation functions will be a straight forward generalization of the above procedure giving the function in the form: n= n x × n y Where: 1,2,... ,n x j= 1,2,... ,n y m= 1,2,. ..,n This function needs to satisfy the conditions: Which will result in a quartet of shape functions in the form:

The Derivatives
In the problems that make use of the shape functions described in the previous section, the finite element model usually requires the first and second derivatives of the shape function to perform the required calculations. In this section, we will present those derivatives for the 1-D problem without elaborations. Table 1 presents the change of the values of the minimum Eigenvalue of the stiffness matrix generated for a bar element. If we ignore the numbers that have an absolute value less than 10 -10 considering them as a numerical zero, we may still find that increasing the number of nodes per element start to introduce negative Eigenvalues until we reach the failure criterion set in this work as 10 -4 . Note that, unpredictably, the exact integration method failed before the numerical integration at 15 nodes per element. On the other hand, the Lagrange polynomial method, which does not use the transformation matrix, was able to produce satisfactory results up to 23 nodes per element which approaches the limit of the 12 point numerical integration technique used. Table 2 presents the results obtained for a beam element. Again we find that the exact integration and numerical integration elements, both, failed around the 18 and 16 DOF respectively which coincides with the number of DOF at which failure occurred in the bar element. Meanwhile, the Modified Lagrange method was able to continue all the way up to 24 DOF which reaches the limit imposed by the numerical integrator.    Table 3 presents the results for a plate bending problem. The same patterns observed in the bar and beam elements can be observed in the plate problem for the modified Lagrange case.

CONCLUSIONS
Several problems were examined in this work to demonstrate the limitations imposed on the creation of super elements with high number of nodes and degrees of freedom. The element matrices were generated using simple, Lagrange, and modified Lagrange polynomials and the integration was performed numerically using Gauss-Lagrange quadrature or exact when possible. Problems involving 1-D elements with 1 or 2 DOF per node and 2-D problems with 4 DOF per node were examined by increasing the number of nodes per element until the lowest (negative) Eigen value of the stiffness matrix had an absolute value greater than 10 -4 . From the results obtained above we may conclude the following: ➢ Automated generation of higher order isoperimetric C 0 and C 1 continuous element model was enabled using an open source numerical manipulator (Octave®) using the different methods presented in this work. ➢ Generating higher order elements is computationally expensive compared to lower ones. Thus, the h-version is more efficient for the same accuracy than the p-version.
➢ Using numerical integration to evaluate the element matrices is efficient and accurate enough for most practical purposes ➢ Using Lagrange and modified Lagrange polynomial increases the stability of the results for higher order element problems when they become a necessity to use. In such cases, the limitation on the results' accuracy will be imposed by the accuracy of the numerical integration scheme.
Further work with the modified Lagrange polynomials, proposed in this work, is needed to enable the inclusion of higher order derivatives in the interpolation polynomials. Such research will help in the generation of elements with the needed derivatives without falling into the trap of the ill-conditioned transformation matrix.