# O.V. Ushakova. On the development of the variational approach to the generation of optimal grids (a survey) ... P. 217-247

A survey of the more than a half-century development of the variational approach to the generation of optimal grids suggested by A. F. Sidorov is presented in the paper. The idea of the approach is based on the requirements that the grid is close to a uniform orthogonal grid and is adjusted to a given function or to the solution of partial differential equations; these requirements are chosen as optimality criteria. The implementation of this idea for the generation of structured grids in two- and three-dimensional domains of geometrically complex shape is given. The developed grid generation algorithms and their applications are described. The survey is divided into two periods: the years of Sidorov's life and the subsequent years. The constructions of the functionals that formalize the grid optimality criteria are presented in relation to a unified technology created in the second period for the numerical simulation of vortex processes in multicomponent hydrodynamics. Examples of grid calculations are given using the currently developed grid generation algorithm in volumes obtained by deformations of volumes of revolution by generalizations of volumes of revolution. A volume of revolution is understood as a shape formed by the rotation of a plane generatrix consisting of segments of straight lines, arcs of circles, and ellipses, called elements, by $180^\circ$ around an axis. A generalization of a volume of revolution is a volume formed by surfaces obtained by rotating elements of plane generatrices by $180^\circ$ about parallel axes. A deformed volume of revolution is a volume obtained by deforming a volume of revolution by another volume of revolution or by a generalization of the volume of revolution. The cases of volumes of revolution, generalizations of volumes of revolution, and volumes of revolution deformed by volumes of revolution have formed the described grid generation technology. A basic structure in the technology is a volume of revolution, which made it possible to carry out its further development in the direction of complication of shapes of domains. At present, it is possible to build structured grids in very complicated three-dimensional  domains. This possibility appeared due to the application of the moving grid technique, which is naturally implemented in variational constructions, and also due to the development of a nonstationary algorithm that deforms a volume of revolution up to a desired deformed shape and deforms and optimizes the grid in order to satisfy the optimality criteria.

Keywords: structured grids, optimal grids, moving grids, generation of grids in deformed volumes

Revised March 13, 2023

Accepted March 20, 2023

Olga Vasil’evna Ushakova, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: uov@imm.uran.ru

REFERENCES

1.   Serezhnikova T.I., Sidorov A.F., Ushakova O.V. On one method of construction of optimal curvilinear grids and its applications. Soviet Journal of Numerical Analysis and Mathematical Modelling, 1989, vol. 4, no. 2, pp. 137–155. doi: 10.1515/rnam.1989.4.2.137

2.   Khairullina O.B., Sidorov A.F., Ushakova O.V. Variational methods of construction of optimal grids. In: Handbook of grid generation / eds. J.F. Thompson, B.K. Soni, N.P. Weatherill, Boca Raton, London, NY, Washington: CRC Press, 1999, pp. 36-1–36-25.

3.   Sidorov A.F. On an algorithm for computation of optimal difference nets. Trudy Matematicheskogo Instituta imeni V.A. Steklova, 1966, vol. 74, pp. 147–151 (in Russian).

4.   Potugina I.V. Mastering and developing the methodology of programs for calculating one-dimensional problems of energy release at VNIIEF (1954–1986). Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1998, iss. 2, pp. 50–59 (in Russian).

5.   Shirokovskaya O.S. Some notes on the paper of A. F. Sidorov “An algorithm for the calculation of optimal difference nets”. USSR Computational Mathematics and Mathematical Physics, 1969, vol. 9, iss. 2, pp. 293–295. doi: 10.1016/0041-5553(69)90112-8

6.   Tikhonov A.N., Samarskii A.A. Homogeneous difference schemes on non-uniform nets. USSR Computational Mathematics and Mathematical Physics, 1963, vol. 2, iss. 5, pp. 927–953. doi: 10.1016/0041-5553(63)90505-6

7.   Emel’yanov K.V. Applying optimal difference grids to problems with singular perturbations. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 1994, vol. 34, no. 6, pp. 936–943 (in Russian).

8.   Emel’yanov K.V. On optimal grids and their application to the solution of problems with a singular perturbation. Russian Journal of Numerical Analysis and Mathematical Modelling, 1995, vol. 10, no. 4, pp. 299–309. doi: 10.1515/rnam.1995.10.4.299

9.   Sidorov A.F. On one algorithm for calculating curvilinear grids that are close to uniform. Chislennye Metody Mekhaniki Sploshnykh Sredy, 1977, vol. 8, no. 4, pp. 149–156 (in Russian).

10.    Khairullina O.B. Method of constructing block regular optimal grids in two-dimensional multiply-connected domains of complex geometries. Russian Journal of Numerical Analysis and Mathematical Modelling, 1996, vol. 11, no. 4, pp. 343–358. doi: 10.1515/rnam.1996.11.4.343

11.   Sidorov A.F., Khairullina O.B., Khairullin A.F. Parallel algorithms of generation of optimal multi-block-structed two-dimensional and three-dimensional grids of large size. In: Numerical grid generation in comput. field simulation / eds. M. Cross, B.K. Soni, J.F. Thompson, J. Hauser, P.R. Eiseman, Mississippi State: ISGG, 1998, pp. 759–769.

12.   Artyomova N.A., Khairullin A.F., Khairullina O.B. Parallel algorithm for calculating optimal grids. Vychislitel’nye Tekhnologii, 2001, vol. 6, no. 2, pp. 3–13 (in Russian).

13.   Ushakova O.V. Efficient algorithm and program LADA for generation of two-dimensional curvilinear optimal adaptive grids in simply-connected domains of geometrically complex forms. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1994, iss. 3, pp. 47–56 (in Russian).

14.   Ushakova O.V. Parallel algorithm and programm for generation of optimal adaptive grids. In: Algorithms and software for parallel computing, Sbornik nauchnyh trudov, Yekaterinburg, 1995, pp. 182–194 (in Russian).

15.   Ushakova O.V. Algorithm of two-dimensional optimal grid generation. In: Numerical grid generation in comput. field simulation: proc. 5th intern. conf. / eds. B.K. Soni, J.F. Thompson, vol. 1, Mississippi State: Mississippi State University, 1996, pp. 37–46.

16.   Rvachev V.L. Theory of R-functions and some applications. Kiev: Naukova Dumka, 1982, 552 p. (in Russian).

17.   Gasilova I.A. Algorithm of automatic generation of an initial approximation of a grid for star type domains. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1994, iss. 3, pp. 33–40 (in Russian).

18.   Sidorov A.F. Examples of exact construction of geometrically optimal two-dimensional grids. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1994, iss. 4, pp. 18–22 (in Russian).

19.   Rubina L.I. Examples of exact solution of the problem for generation of three-dimensional optimal grids. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1995, iss. 4, pp. 37–41 (in Russian).

20.   Khairullina O.B. Calculation of stationary subsonic vortical flows of ideal gas in symmetric channels of complex geometries. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1990, iss. 3, pp. 32–39 (in Russian).

21.   Ahmadeev V.F., Sidorov A.F., Spiridonov F.F., Khairullina O.B. On three methods of numerical modelling of subsonic flows in symmetric channels of complex form. Modelirovanie v Mekhanike, 1990, vol. 4 (21), no. 5, pp. 15–25 (in Russian).

22.   Khairullina O.B. To the calculation of flow of gas in channels of complex configuration. Prikladnaya matematika i matematicheskaya fizika, 1996, vol. 37, no. 2, pp. 103–108 (in Russian).

23.   Khairullina O.B. Modelling subsonic vortex gas flows in channels of complex geometries. Russian Journal of Numerical Analysis and Mathematical Modelling, 1998, vol. 13, no. 3, pp. 191–219.

24.   Kokovikhina O.V., Sidorov A.F., Khairullina O.B. Mathematical modelling of gas-dynamic and acoustic effects in combustion chambers. In: Theory of combustion of powder and explosives / ed. A.M. Lipanov, NY: Nova Science, 1996. pp. 191–202.

25.   Anuchina N.N., Volkov V.I., Gordeychuk V.A., Es’kov N.S., Ilyutina O.S., Kozyrev O.M. Numerical simulation of 3D multi-component vortex flows by MAH-3 code. In: Advances in grid generation / ed. O.V. Ushakova, NY: Nova Science, 2007, pp. 337–380.

26.   Koshkina T.N. (Bronina T.N.), Sidorov A.F. On one geometrical way of construction of three-dimensional difference grids. In: Numerical and analytical methods for solving problems of continuum mechanics, sbornik trudov, Sverdlovsk: Urals Scientific Center, USSR Acad. Sci., 1981, pp. 91–100 (in Russian).

27.   Shabashova T.I. On the generation of optimal curvilinear coordinate grids in three-dimensional domains. Chislennye Metody Mekhaniki Sploshnykh Sredy, 1986, vol. 17, no. 1, pp. 144–155 (in Russian).

28.   Controlled fusion / ed. J. Killeen, London, NY, San Francisco: Acad. Press, 1976. Translated to Russian under the title Upravlyaemyi termoyadernyi sintez, Moscow: Mir, 1980.

29.   Ushakova O.V. Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells. SIAM Journal on Scientific Computing, 2001, vol. 23, iss. 4, pp. 1289–1273.

30.   Ushakova O.V. Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 2001, vol. 41, no. 6, pp. 881–894 (in Russian).

31.   Ushakova O.V. On nondegeneracy of three-dimensional grids. Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2004, pp. S78–S100.

32.   Johnen A., Weill J.C., Remacle J.F. Robust and efficient validation of the linear hexahedral element. Procedia Engineering, 2017, vol. 203, pp. 271–283. doi: 10.48550/arXiv.1706.01613

33.   Bobylev N.A., Ivanenko S.A., Kazunin A.V. On piecewise-smooth homeomorphic mappings of bounded domains and their applications to the theory of grids. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 2003, vol. 43, no. 6, pp. 808–817 (in Russian).

34.   Farin G. Curves and surfaces for computer aided geometric design, A practical guide. Fourth edition. NY: Acad. Press., 1997.

35.   Knabner P., Summ G. The invertibility of the isoparametric mapping for pyramidal and prismatic finite elements. Numerische Mathematik, 2001, vol. 88, pp. 661–681. doi: 10.1007/PL00005454

36.   Knabner P., Korotov S., Summ G. Conditions for the invertibility of the isoparametric mapping for hexahedral finite elements. Finite Elements in Analysis and Design, 2003, vol. 40, iss. 2, pp. 159–172. doi: 10.1016/S0168-874X(02)00196-8

37.   Vavasis S.A. A Bernstein–Bezier sufficient condition for invertibility of polynomial mapping functions: e-resource (November 3, 2001). Available on https://arxiv.org/pdf/cs/0308021.pdf .

38.   Bronina T.N., Gasilova I.A., Ushakova O.V. Algorithms for constructing three-dimensional structured grids. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 2003, vol. 43, no. 6, pp. 875–883 (in Russian).

39.   Thompson J.F., Warsi Z.U.A., Mastine C.W. Numerical grid generation: foundation and applications, NY: Elsevier, 1985, 502 p.

40.    Ushakova O.V. Classification of hexahedral cells. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 2008, vol. 48, no. 8, pp. 1426–1428 (in Russian). doi: 10.1134/S096554250808006X

41.   Advanaces in grid generation / ed. O.V. Ushakova, NY: Nova Science, 2007. 382 p.

42.   Artyomova N.A., Khairullin A.F., Khairullina O.B. Generation of curvilinear grids in multiply connected domains of complex topology. In: Advances in grid generation / ed. O.V. Ushakova, NY: Nova Science, 2007, pp. 161–188.

43.   Martyushov S.N. The method MODAMS for calculating ideal gas flows around bodies by final volume technique. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 1998, iss. 2, pp. 49–56 (in Russian).

44.   Azarenok B.N. Conservative remapping on hexahedral meshes. In: Advances in grid generation / ed. O.V. Ushakova, NY: Nova Science, 2007, pp. 337–379.

45.   Azarenok B.N. A conservative interpolation method on hexahedral grids. Matematicheskoe modelirovanie, 2008, vol. 20, no. 2, pp. 59–75 (in Russian).

46.   Dukowicz J.K., Padial N.T. REMAP3D: A conservative three-dimensional remapping code: Technical Report. Oak Ridge: Technical Information Center Oak Ridge Tennessee, 1991. NTIS Issue Number 199201. 38 p.

47.   Prokhorova M.P. Problems of homeomorphism arising in the theory of grid generation. Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2008, pp. S165–S182. doi: 10.1134/S0081543808050155

48.   Ushakova O.V. Nondegeneracy tests for hexahedral cells. Computer Methods in Applied Mechanics and Engineering, 2011, vol. 200, iss. 17–20, pp. 1649–1658. doi: 10.1016/j.cma.2011.01.014 .

49.   Ushakova O.V. Criteria for hexahedral cell classification. Applied Numerical Mathematics, 2018, vol. 127, pp. 18–39. doi: 10.1016/j.apnum.2017.12.012

50.   Bronina T.N. Algorithm for constructing initial three-dimensional structured grids for the domains of revolution. Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2008, pp. S36–S43. doi: 10.1134/S00815480805004X

51.   Ushakova O.V. Optimization algorithms for three-dimensional grids in domains of rotations. Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2008, pp. S228–S259. doi: 10.1134/S0081543808050192

52.   Godunov C.K., Zabrodin A.V., Ivanov M.Ya., Kraiko A.N., Prokopov G.P. Numerical solution of multi-dimensional problems of gasdynamics. Moscow: Nauka Publ., 1976. 400 p (in Russian).

53.   Knupp P.M., Steinberg S. Fundamentals of grid generation. Boca Raton, FL: CRC Press, 1994.

54.   Liseikin V.D. Grid generation methods. Berlin: Springer, 1999.

55.   Kurant R. Partial differential equations, NY: Wiley, 1962. Translated to Russian under the title Uravneniya s chastnymi proizvodnymi, Moscow: Mir, 1964.

56.   Sidorov A.F., Shabashova T.I. On one method of computation of optimal difference grids for multidimensional domains. Chislennye Metody Mekhaniki Sploshnykh Sredy, 1981. vol. 12, no. 5, pp. 106–123 (in Russian).

57.   Ushakova O.V. Theorem on existence and uniqueness of the solution of the boundary value problem for constructing one-dimensional optimal adaptive grids. Modelirovanie v Mekhanike, 1989, vol. 3, no. 2, pp. 134–141 (in Russian).

58.   Ivanenko C.A., Charakhch’yan A.A. Curvilinear grids of convex quadrilaterals. USSR Computational Mathematics and Mathematical Physics, 1988, vol. 28, no. 2, pp.  126–133. doi: 10.1016/0041-5553(88)90157-7 .

59.   Ivanenko S.A. Selected chapters on grid generation and applications. Moscow: Dorodnicyn Computing Centre of the Russian Academy of Sciences Publ., 2004.

60.   Dobrev V., Knupp P., Kolev T., Mittal K., Tomov V. hr-Adaptivity for nonconforming high-order meshes with the target matrix optimization paradigm. Engineering with Computers, 2022, vol. 38, pp. 3721–3737. doi: 10.1007/s00366-021-01407-6

61.   Dobrev V., Knupp P., Kolev T., Mittal K., Tomov V. The target-matrix optimization paradigm for high-order meshes. SIAM Journal on Scientific Computing, 2019, vol. 1, pp. B50–B68. doi: 10.1137/18M1167206

62.   Mittal K., Fischer P. Mesh smoothing for the spectral element method. Journal of Scientific Computing, 2019, vol. 78, pp. 1152–1173. doi: 10.1007/s10915-018-0812-9

63.   Turner M., Peiro J., Moxey D. Curvilinear mesh generation using a variational framework. Computer-Aided Design, 2018, vol. 103, pp. 73–91. doi: 10.1016/j.cad.2017.10.004

64.   Xu K., Gao X., Chen G. Hexahedral mesh quality improvement via edge-angle optimization. Computers and Graphics, 2018, vol. 70, pp. 17–27. doi: 10.21203/rs.3.rs-586657/v1

65.   Zhu Y., Bridson R., Kaufman D.M. Blended cured quasi-newton for distortion optimization. ACM Transactions on Graphics, 2018, vol. 37, no. 4. doi: 10.1145/3197517.3201359

66.   Ushakova O.V. An algorithm of correcting a grid with respect to the surface of revolution. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2016, iss. 1. pp. 16–27 (in Russian).

67.   Ushakova O.V. Application of the algorithm of correcting a grid with respect to the surface of revolution. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2016, iss. 2, pp. 31–37 (in Russian).

68.   Ushakova O.V., Artyomova N.A., Bronina T.N., Anuchina A.I., Gordeichuk V.I. Grid generation in deformed volumes of revolution. In: International conference “Advanced mathematics, computations and applications 2015” (AMCA-2015), dedicated to the 90th anniversary of the birthday of academician Marchuk G.I., Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk: Abvey Publ., 2015, pp. 782–788.

69.   Zegeling P.A. Moving grid techniques. In: Handbook of grid generation / eds. J.F. Thompson, B.K. Soni, N.P. Weatherill, Boca Raton, London, NY, Washington: CRC Press, 1999, pp. 37-1–37-22.

70.   Staten M.L., Owen S.J., Shontz S.M., Salinger A.G., Coffey T.S. A comparison of mesh morphing methods for 3D shape optimization. In: Proceedings of the 20th international meshing roundtable / eds. W.R. Quadros, Berlin, Heidelberg: Springer, 2011, pp. 293–311.

71.   Immonen E. A parametric morphing method for generating structured meshes for marine free surface flow applications with plane symmetry. Journal of Computational Design and Engineering, 2019, vol. 6, pp. 348–353. doi: 10.1016/j.jcde.2018.11.002

72.   Biancolini M.E., Chiappa A., Giorgetti F., Porziania S., Rochette M. Radial basis functions mesh morphing for the analysis of cracks propagation. Procedia Structural Integrity, 2018, vol. 8, pp. 433–443.

73.   Prokopov G.P. Moving mesh calculation in unsteady two-dimensional problems. In: Advances in grid generation / ed. O.V. Ushakova, NY: Nova Science, 2007, pp. 127–160.

74.   Artemova N.A. A nonstationary algorithm of constructing structured grids in deformed regions. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2018, iss. 4, pp. 76–86 (in Russian).

75.   Ushakova O.V. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2018, iss. 1, pp. 30–41 (in Russian).

76.   Anuchina A.I., Artyomova N.A., Gordeychuck V.A., Ushakova O.V. A technology for grid generation in volumes bounded by the surfaces of revolutions. In: Numerical geometry, grid generation and scientific computing: Proceedings of the 9th international conference NUMGRID 2018 / Voronoi 150, eds. V.A. Garanzha, L. Kamenski, H. Si, Lecture Notes in Computational Science and Engineering, 2019, vol. 131, pp. 281–292. doi: 10.1007/978-3-030-23436-2_21

77.   Artemova N.A., Ushakova O.V. On the development of a grid generation algorithm for deformed solids of revolution formed by several surfaces. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2020, iss. 4, pp. 86–96 (in Russian).

78.   Ushakova O.V. An algorithm of correcting a grid with respect to a deformed domain of revolution. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2017, iss. 2, pp. 53–65 (in Russian).

79.   Anuchina A.I., Artyomova N.A., Gordeychuck V.A., Ushakova O.V. The algorithm for generation of structured grids in deformed volumes of revolution. Journal of Physics: Conference Series, 2019, vol. 1392, article no. 012029. doi: 10.1088/1742-6596/1392/1/012029

80.   Anuchina A.I., Artyomova N.A., Gordeychuck V.A., Ushakova O.V. On the development of the grid generation technology for constructions bounded by the surfaces of revolutions. AIP Conference Proceedings, 2020, vol. 2312, article no. 050002. doi: 10.1063/5.0035688

81.   Artyomova N.A., Ushakova O.V. About grid generation in constructions bounded by the surfaces of revolution. Journal of Physics: Conference Series, 2021, vol. 2099, article no. 012018. doi: 10.1088/1742-6596/2099/1/012018

82.   Ushakova O.V., Artyomova N.A. Non-stationary grid generation algorithm for deformed volumes of revolution. Mathematics and Computers in Simulation, 2023, vol. 203, pp. 878–909. doi: 10.1016/j.matcom.2022.07.016

83.   Ushakova O.V. Realization of an adaptation criterion in grid generation technology for constructions bounded by surfaces of revolution with parallel axes of revolution. Numerical Analysis and Applications, 2023, vol. 16, no. 1, pp. 74–78. doi: 10.1134/S199542392301007X

84.   Ushakova O.V., Artemova N.A. Grid generation technologies for constructions bounded by the surfaces of revolution with parallel axes of revolution. Vestnik Bashkirskogo universiteta, 2022, vol. 27, no. 3, pp. 541–546 (in Russian). doi: 10.33184/bulletin-bsu-2022.3.9

85.   Ushakova O.V. Adaptation criterion implementations in optimal grid constructing algorithm. Voprosy atomnoi nauki i tekhniki. Ser. Matematicheskoe modelirovanie fizicheskikh protsessov, 2021, iss. 2, pp. 80–95 (in Russian).

86.   Liseikin V.D. A survey of methods for constructing structured adaptive grids. Computational Mathematics and Mathematical Physics, 1996, vol. 36, no. 1, pp. 1–32.

Cite this article as: O.V. Ushakova. On the development of the variational approach to the generation of optimal grids (a survey). Trudy Instituta Matematiki i Mekhaniki URO RAN, 2023, vol. 29, no. 2, pp. 217–247.

[References -> on the "English" button bottom right]