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).