The sample under consideration has to be descretized in the three dimensions of space. This is achieved by its division into sufficiently small finite elements, which can have the shape of cubes, hexahedrons or tetrahedrons.

Usually the initial triangulation is a uniform mesh, consisting of a suitable number of elements and nodes. If no refinement is applied, this initial mesh is of great importance for the whole simulation. A small number of elements and nodes limits the achievable accuracy and reliability and implies poor approximation near singularities and internal or boundary layers. On the other hand if a finer mesh is chosen, accuracy can be improved significantly but at the same time the systems of equations enlarge, which may lead to intolerably long computation times.

There are several methods to improve the results and almost preserve the calculations' complexity (cf. [Kiku86]). First the nodes of the finite element grid can be relocated which leads to a higher density of nodes in areas with larger integration errors. The number of elements remains fixed but they are deformed. This may lead to undesired shapes and deteriorating convergence rates. As an alternative the degrees of polynomials used for the interpolation of the desired function can be changed.

Finally, the number of unknowns can be optimized by fitting the corresponding discretization to the present approximate solution. In regions where improved accuracy is needed, the underlying discretization mesh is refined and new elements and vertices are inserted. (In this paper vertex and node are used as synonyms.) However, where the solution is expected to be smooth, it is possible to coarsen the mesh. To decide whether an element has to be refined or not the error which originates from the discretization of integrations has to be estimated for each element.

Methods which use this technique are called multi-level methods. They have been proven to be of optimal or nearly optimal complexity for the solution of discrete systems arising from partial differential equations.