6.2.1 Mesh Refinement

The requirements for a suitable finite element mesh have already been discussed in Sec. 2.4. In order to reduce the size of the initial finite element mesh, global or partial (adaptive) mesh refinement can be done at run time. Yet, in parallel programs adaptive refinement methods give rise to another difficulty and that is ``load balancing'' [70]. In order to get the maximum speed up, each processor working for a parallel program should be busy all the time, because delays and idle times reduce the overall performance. Therefore, the problem is initially split up into parts, which will give each processor the same amount of work. To be more accurate, in a heterogeneous environment where machines and processors with different speeds and capabilities are used, the numerical problem has to be distributed in such a way, that all processors finish their tasks at the same time. Then they do not have to wait for each other, when they have to synchronize their results. Adaptive mesh refinement methods insert and remove finite elements (and therefore nodes) and modify the number of unknowns at run time. Thus, the computational effort will increase for processors working on a partition of the finite element mesh, where elements have been inserted, and decrease for those, where elements have been removed. Of course, this disturbs the initial load balancing and requires a new partitioning of the finite element mesh, redistribution of the current data to the processors and reinitialization before the calculation can be resumed. This scheme has been implemented in the finite element package ``UG'' [71,72], whose data model is based on ``Dynamic Distributed Data'' [73], a software tool for distributed memory parallelization.

Nevertheless, global mesh refinement has been implemented, because it allows much smaller input data files and adds the flexibility of increasing the mesh resolution without remeshing the model with a mesh generator. The global refinement scheme is very simple, because it just splits up every finite element into eight ``children'' (cf. Fig. 6.1) [16]. The details of the implementation are discussed in Sec. 6.2.1. If this scheme is applied to the whole finite element mesh, its structure remains consistent. The quality of the mesh is preserved, because the four children in the corners of the parent element are congruent to the parent and the other four from the octahedron in the center have equal volumes, too. Even though they are not congruent with the parent, it has been shown, that at most three congruence classes occur. Thus, the stability of the generated triangulations is preserved. With every refinement step the number of finite elements increases by a factor of eight and the number of nodes approximately, too.

Figure 6.1: Global refinement of a ``parent'' tetrahedral finite element (thick lines) into eight ``children'' [16].

As a result, the input data files and especially the file containing the mesh geometry are much smaller. Even more important, the mesh generator does not have to generate a very fine and therefore large mesh, even though it has to be fine enough to resolve the details of the geometrical model and should give finite elements of good quality. Moreover, convergence of the results can be ``easily'' checked with a refined finite element mesh.