Automatic mesh refinement and data structure for multigrid finite elements techniques

A general algorithm for locally refining any conforming triangulation to generate a new conforming one is presented. The proposed algorithm ensures that all angles in subsequent refined triangulations are greater than, or equal to, half the smallest angle in the original triangulation, the shape regularity of all triangles is maintained and the transition between small and large triangles is smooth. The generated triangulations are nested, so it is possible to implement the approach with adaptive and/or multigrid techniques. A complete algorithm for solving two-dimensional elliptic boundary value problems adaptively by multigrid is presented. The development and implementation of the main parts of this algorithm; automatic mesh generator, a posteriori error estimator, refinement strategy and the multigrid solver are presented in some detail. An appropriate data structure is developed to meet the excess data required for the generation process also to keep track of different grid levels. By the aid of this data structure, it becomes easy to design simple algorithms to store only the non-zero elements of stiffness matrices for different grids and to design a very simple multigrid transfer operator. Numerical examples are presented to show the generated grid sequence for two different boundary value problems. (C) 1987 Published by Elsevier Science Ltd.