Keywords: finite elements, variational problems, mesh optimization, tetrahedral elements, node movement, edge swapping, node insertion.

In this paper we present an extension of our work on mesh optimization presented at the last Engineering Computational Technology conference in September 2000 from two space dimensions to three. The approach that we follow is to consider the adaptive finite element solution of a general class of variational problems using a combination of node movement, edge swapping, face swapping and node insertion. The particular adaptive scheme that is used is based upon the construction of a hierarchy of locally optimal tetrahedral meshes starting with a coarse grid for which the location and connectivity of the nodes is optimized. This grid is then locally refined and the new mesh is optimized in the same manner. Results presented indicate that, as with triangles in two dimensions, this approach is able to produce better meshes of tetrahedra than those obtained by more conventional adaptive strategies and in a relatively efficient manner.

The class of problem that we consider in this work may be posed in the following form (or similar, according to the precise nature of the boundary conditions):

for some energy density function . Here is the dimension of the problem and is the dimension of the dependent variable . Physically this variational form may be used to model problems in linear and nonlinear elasticity, heat and electrical conduction, motion by mean curvature and many more. Throughout this paper we restrict our attention to the three-dimensional case where .

For variational problems of the form (11.1), the fact that the exact solution minimises the energy functional provides a natural optimality criterion for the design of computational grids using -refinement. Indeed, the idea of locally minimising the energy with respect to the location of the vertices of a mesh of fixed topology has been considered by a number of authors, as has the approach of locally minimising the energy with respect to the connectivity of a mesh with fixed vertices. All of this work has been undertaken in only two space dimensions however and, to our knowledge, this is the first work in which mesh optimization with respect to the solution energy has been attempted for unstructured tetrahedral meshes in three space dimensions.

The algorithm that we use consists of a number of sweeps through each of the nodes in turn until convergence is achieved. At the beginning of each sweep the gradient, with respect to the position of each node, of the energy functional

is found (where is the latest piecewise linear finite element solution). When each node , with location say, is visited the direction of steepest decent,

is used in order to determine along which line the node should be moved. The distance that the node is moved along this line is computed using a one-dimensional minimization of the energy subject to the constraint that the node should not move more than a proportion () of the distance from its initial position to its opposite face. Once a new position for the node has been found the value of the solution, say, at that node must be updated by solving the local problem

Here is the union of all elements which have node as a vertex and Dirichlet conditions are imposed on using the latest values for . Once this update is complete the same process is undertaken for the next node in the sorted list and when each node has been visited the sweep is complete. Provided convergence has not been achieved the next sweep may then begin.

Once convergence with respect to the position of each node has been achieved a further reduction in the energy of the solution is sought by the use of edge and face swapping. In three dimensions there are a large number of different ways in which the local connectivity of the nodes may be altered. In this work we use the same edge and face swapping stencils as the public domain software package GRUMMP, whose implementation is restricted to improving the geometric quality of the mesh rather than minimizing energy as we do here.

Of course the positions of the nodes are likely to be no longer locally optimal at this point due to the edge/face swapping. Hence it is necessary to alternate between the node movement and the swapping algorithms until the whole process has converged (at least approximately). At this stage we allow the application of local mesh refinement to obtain a new mesh at the next level which must itself now be optimized. The process is complete when either a desired accuracy has been obtained or a maximum number of nodes or elements has been reached.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)