Mat-1.3656 Seminar on numerical analysis and computational science

Monday Jan 28, 2008, room U322 at 14.15


Dr. V.A. Garanzha:
Variational mesh optimization based on  quasi-isometric mappings and discrete curvatures.  

In order to provide rigorous foundations for construction of optimal meshes in numerical analysis, the concepts from three major fields are considered:

- concepts of nonregular riemannian geometry such as intrinsic and extrinsic curvatures of nonregular manifolds, approximation by polyhedral manifolds, cut and paste operations, parameterizations of nonregular manifolds [1], [2], [3];

- concepts of mathematical elasticity: polyconvexity and well-posed variational problems for construction of invertible mappings [4];

- concept of duality (or polarity), based on Legendre-Young-Fenchel transform [5], with applications to error estimation and duality of Delaunay and Voronoi partitionings.


We consider the mesh to be optimal if it can be considered as a quasi-isometric mapping with minimal equivalence constant (minimal distortion) between manifolds of bounded curvature.  Such a mapping can be constructed by gluing together local mappings inside each mesh cell. Apriori definition of mesh cell shapes and sizes (such as apriori mesh  stretching in boundary layers) is equivalent to definition of nonregular manifold with intrinsic metric via  cut and paste operations. This manifold is an argument of quasi-isometric mapping and can be called parameteric manifold or parameteric space for computational mesh. Local coordinates on this manifold are frozen into mesh hence they can be called Lagrange coordinates. Adaptation metric defined in the computational domain defines another nonregular manifold with intrinsic metric being the image of the first one under quasi-isometric mapping. Local coordinates in this manifolds can be called Euler coordinates.

Multidimensional variational principle for construction of such mappings and quasi-minization of equivalence constant is available [10]. Existence theorem [11] for this variational principle states that if the set of admissible mappings is not empty, then minimizer exists and is quasi-isometric mapping.

For mappings between 2d manifolds of bounded curvature (MBC), existence of addmissible mappings follows from results on bilipschitz equivalence of 2d MBC [6], [7], [8], [9]. Analysis of certain properties of MBC, such as positive and negative curvature, constants from extremal isoparametric inequality, etc. allows to predict equivalence constant (in other words, distortion of optimal mesh) [12].

Convergence of gradient search method for minimization of discrete quasi-isometric functional can be rigorously proved for quite general sets of local mappings. It was proved also that minimizer of discrete functional in invertible quasi-isometric mapping.  Polyconvexity leads to local convexity of discrete functional (minimization problem for each mesh node is convex). Discrete functionals were investigated for the case of picewise linear mappings of standard triangular and tetrahedral meshes, and for the more complex cases, including hexahedral meshes (trilinear local mappings), curvilinear meshes (local mappings based on Bernstein-Bezier polynomials), as  well as general polyhedral meshes [14]. The last case is particularly interesting because definition of target polyhedral cell shapes based on  the concept of 3d dicrete curvatures (say, total variation of Regge action) allows for regular and semiregular polyhedra, such as Platonic and Archimedian solids, as well as regular prisms and antiprisms to become exact minimizers of discrete functional.


1. A.D. Alexandrov and V.A. Zalgaller,
Two-dimensional manifolds of bounded curvature. Tr. Math. Inst.
Steklova, v. 63 (1962). English transl.: Intrinsic geometry of
surfaces. Transl. Math. Monographs v.15, Am. Math. Soc. (1967),
Zbl.122,170.

2. Yu. Reshetnyak. Two-Dimensional Manifolds of Bounded Curvature.
In: Reshetnyak Yu.(ed.), Geometry IV
(Non-regular Riemannian Geometry), pp. 3-165. Springer-Verlag, Berlin (1991).

3. Bakelman, I. Ya. Verner, A. L., Kantor, B. E. {Vvedenie v
differentsialnuyu geometriyu "v tselom"}. (in Russian) [Introduction
to differential geometry "in the large"]  ``Nauka'', Moscow, 1973. 440
pp.

4. Ball J.M. Convexity conditions and existence theorems in nonlinear
elasticity // Arch. Rat. Mech.
Anal. 1977. V. 63. P. 337--403.

5. Fenchel W. On conjugate convex functions // Canad. J. Math. 1949.
V.1. P.73-77.

6. I.Ya. Bakelman. Chebyshev nets in manifolds of bounded curvature.
Tr. Math. Inst. Steklova,
v. 76, 124-129 (1965).English transl.: Proc. Steklov Inst. Math. v.
76, 154-160(1967), Zbl104,168.

7. M. Bonk and U. Lang. Bi-Lipschitz parameterization of surfaces.
Mathematische Annalen, 2003, DOI 10.1007/s00208-003-0443-8.

8. A. Belenkiy, Yu. Burago. Bi-Lipschitz equivalent Alexandrov
surfaces, I,  arXive:math. DG/0409340. 2003.

9. Yu. Burago. Bi-Lipschitz equivalent Alexandrov surfaces, II,
arXive:math. DG/0409343. 2003.

10. V.A. Garanzha. Barrier variational generation of quasi-isometric grids.
Computational Mathematics and Mathematical Physics, 2000;  v. 40
(11):1617--1637.

11. V.A. Garanzha. Existence and invertibility theorems for the
problem of the variational construction of quasi-isometric mappings
with free boundaries.  Comput. Math. Math. Phys. 45 (2005), no. 3,
465--475

12. V.A. Garanzha.  Variational principles in grid generation and
geometric modeling: theoretical justifications and open problems.
Numerical Linear Algebra with Applications 2004; v.9 (6-7).

13. V.A. Garanzha. Quasi-isometric surface parameterization. Applied
Numerical mathematics. 2005.  V.55, No.3, pp. 295-311.

14. V.A. Garanzha. Numerical geometry and grid generation. 593p.
Fizmatkniga, 2008 (in Russian).