CCRAS, Moscow, 181 pp., 1997 (in Russian)


Methods of grid generation based on the theory of harmonic maps are presented. Algorithms for structured and unstructured adaptive grids in two - dimensional and three - dimensional cases as well as for grids on surfaces are described in detail. All methods are based on grid nodes movement (r-refinement).

Two fundamental problems in grid generation are considered.

The first problem is to find conditions on discrete mapping to be nondegenerate. The condition of convexity of all the grid cells in two dimensions is assumed as a discrete analogue of the Jacobian positiveness. It provides the grid to be nondegenerate. Indeed, if all grid cells are convex, then all grid nodes do not leave a domain and such grid does not contain self - intersecting cells. In the three - dimensional case a more complicated analog of the Jacobian positiveness is presented.

The second problem is to develop a suitable theoretical framework for grid generation. The theory of harmonic maps has been chosen as a basis for this purpose. The problem of constructing harmonic coordinates on the surface of the graph of control function is formulated. Harmonic coordinates are constructed from harmonic mapping of the surface onto a parametric square (or cube in the three - dimensional case). The projection of these coordinates onto a physical region produce an adaptive - harmonic grid.

Two methods are used for numerical solution. The first one is based on the finite - difference approximation of Euler equations. The second method is based on a direct minimization of the discrete analog of harmonic functional.

The variational approach has been extended to the case of irregular grids. The main principle can be formulated as follows. Harmonic coordinates are generated by the global harmonic mapping of the physical domain or the surface of control function onto a parametric square. The result will be a regular grid. Irregular (unstructured) grid can be considered as a set of local coordinates, different for each cell or element. Hence, each cell, for example a quadrilateral, can be harmonically mapped onto the same auxiliary unit square. The total irregular grid with fixed connections can be computed minimizing the sum of harmonic functionals, written for each grid cell. This will be a smoothing and adaption stage in the method of irregular grid generation. For triangular grids each triangle should be mapped harmonically onto an equilateral triangle and so on.

A very important property of variational approach is that the functionals are approximated in such a way that all their discrete analogues have infinite barrier on the boundary of the set of nondegenerate grids. The resulting algorithms assure generation of nondegenerate grids according to developed discrete conditions of the Jacobian positiveness. Consequently, the theory of harmonic maps, applied to grid generation, can be assumed as a general framework for the development of fully automated algorithms. Moreover, as on continuous level the theory of harmonic maps provides construction of nondegenerate curvilinear coordinates, on discrete level the developed application of this theory guarantees generation of nondegenerate grids in arbitrary domains.

The problem of error minimization is also cosidered. It is shown that adaptive-harmonic grids are optimal for aposteriory estimates. It means that if we use adaptive-harmonic grids, the interpolation error, measured in max-norm is minimized.

Results of test computations are presented.



1. Nondegenerate planar grids.
   1.1 Introductory remarks.
   1.2 Conditions of the one-to-one mapping used for regular grid generation.
   1.3 Conditions for a regular grid to be nondegenerate.
   1.4 Irregular grids.

2. Harmonic planar grids.
   2.1 Priblem formulation.
   2.2 Derivation of equations.
   2.3 Modifications of the Winslow method.
   2.4 Numerical implementation.
   2.5 Variational method for planar harmonic grid generation.
       2.5.1 Problem formulation.
       2.5.2 Approximation of the functional.
       2.5.3 Method of numerical minimization.
       2.5.4 Auxiliary algorithm.
       2.5.5 Derivation of computational formulas.
   2.6 Comparison between the Winslow and variational methods. Results
       of test computations.

3. Harmonic mappings between surfaces. General theory.
   3.1 Introductory remarks.
   3.2 Theory of harmonic maps.
   3.3 Derivation of equations.
   3.4 Properties of harmonic functional
       3.4.1 Harmonic cordinates on the plane.
       3.4.2 Harmonic cordinates on the 2D surface.
       3.4.1 Harmonic cordinates on the 3D surface.

4. Two - dimensional adaptive - harmonic grids.
   4.1 Problem formulation.
   4.2 Regular grids.
       4.2.1 Derivation of equations.
       4.2.2 Numerical implementation.
   4.3 Irregular adaptive-harmonic grids.
       4.3.1 Problem formulation.
       4.3.2 Approximation of the functional.
       4.3.3 Method of numerical minimization.
       4.3.4 Derivation of computational formulas.
   4.4 Comparison between the finite-difference and variational methods.

5. Adaptive-harmonic grids on surfaces.
   5.1 Problem formulation.
   5.2 Regular grids on surfaces.
       5.2.1 Derivation of equations.
       5.2.2 Numerical implementation.
   5.3 Irregular adaptive-harmonic grids on surfaces.
       5.3.1 Problem formulation.
       5.3.2 Approximation of the functional.
       5.3.3 Method of numerical minimization.
       5.3.4 Derivation of computational formulas.
   5.4 Problem of ununiqueness.
   5.5 Comparison between the finite-difference and variational methods
       for adaptive-harmonic grid generation.

6. Three - dimensional adaptive-harmonic grids.
   6.1 Problem formulation.
   6.2 Three - dimensional regular grids.
       6.2.1 Derivation of equations.
       6.2.2 Numerical implementation.
   6.3 Irregular adaptive-harmonic grids in three dimensions.
       6.3.1 Condition on three-dimensional grid to be nondegenerate.
       6.3.2 Problem formulation.
       6.3.3 Approximation of the functional.
       6.3.4 Method of numerical minimization.
       6.3.5 Derivation of computational formulas.
   6.4 Comparison between the finite-difference and variational methods
       for adaptive-harmonic grid generation in three dimensions.

7. Adaptive - harmonic grids and the problem of error minimization.
   7.1 Error estimates in the one - dimensional case.
   7.2 An example of the one - dimensional function with the boundary layer.
   7.3 Error estimates in the two - dimensional case.
   7.4 Results of test computations.
   7.5 Simulation of the wind - induced circulation in North Atlantic.

Appendix A. Program in C++ for regular grid generation in 2D.
Appendix B. Program in C++ for irregular grid generation in 2D.

Robert Schneiders, Lehrstuhl für Angewandte Mathematik, insbesondere Informatik