On the development of the variational approach to the generation of optimal grids (a survey)

O. V. Ushakova

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 2, pp. 217-247

Résumé

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.

Détail

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

Bibliographie

[1] Serezhnikova T.I., Sidorov A.F., Ushakova O.V., “On one method of construction of optimal curvilinear grids and its applications”, Sov. J. Numer. Anal. Math. Modelling, 4:2 (1989), 137–155 | DOI | MR | Zbl

[2] Khairullina O.B., Sidorov A.F., Ushakova O.V., “Variational methods of construction of optimal grids”, Handbook of grid generation, eds. J.F. Thompson, B.K. Soni, N.P. Weatherill, CRC Press, Boca Raton; London; NY; Washington, 1999, 36, 25 pp. | MR

[3] Sidorov A.F., “Ob odnom algoritme rascheta optimalnykh raznostnykh setok”, Tr. Matematicheskogo in-ta im. V.A.Steklova AN SSSR, 74 (1966), 147–151 | Zbl

[4] Potugina I.V., “Osvoenie i razvitie metodiki programm rascheta odnomernykh zadach energovydeleniya vo VNIIEF (1954–1986)”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1998, no. 2, 50–59

[5] Shirokovskaya O.S., “Zamechanie k state A.F. Sidorova “Ob odnom algoritme rascheta optimalnykh raznostnykh setok””, Zhurn. vychisl. matematiki i mat. fiziki, 9:2 (1969), 468–469 | MR | Zbl

[6] Tikhonov A.N., Samarskii A.A., “Odnorodnye raznostnye skhemy na neravnomernykh setkakh”, Zhurn. vychisl. matematiki i mat. fiziki, 2:5 (1985), 812–832

[7] Emelyanov K.V., “Primenenie optimalnykh raznostnykh setok k resheniyu zadach s singulyarnym vozmuscheniem”, Zhurn. vychisl. matematiki i mat. fiziki, 34:6 (1994), 936–943 | MR | Zbl

[8] Emel'yanov K.V., “On optimal grids and their application to the solution of problems with a singular perturbation”, Russ. J. Numer. Anal. and Math. Modelling, 10:4 (1995), 299–310 | DOI

[9] Sidorov A.F., “Ob odnom algoritme rascheta krivolineinykh setok, blizkikh k ravnomernym”, Chisl. metody mekhaniki sploshnoi sredy, 8:4 (1977), 149–156

[10] Khairullina O.B., “Method of constructing block regular optimal grids in two-dimensional multiply-connected domains of complex geometries”, Russ. J. Numer. Anal. Math. Modelling, 11:4 (1996), 343–358 | DOI | MR | Zbl

[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”, Numerical grid generation in comput. field simulation, eds. M. Cross, B.K. Soni, J.F. Thompson, J. Hauser, P.R. Eiseman, ISGG, Mississippi State, 1998, 759–769

[12] Artemova N.A., Khairullin A.F., Khairullina O.B., “Parallelnyi algoritm rascheta optimalnykh setok”, Vychisl. tekhnologii, 6:2 (2001), 3–13 | MR | Zbl

[13] Ushakova O.V., “LADA — ekonomichnyi algoritm i programma postroeniya dvumernykh krivolineinykh optimalnykh adaptivnykh setok v odnosvyaznykh oblastyakh geometricheski slozhnoi formy”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1994, no. 3, 47–56

[14] Ushakova O.V., “Parallelnyi algoritm i programma postroeniya optimalnykh adaptivnykh setok”, Algoritmy i program. sredstva paral. vychislenii, sb. nauch. tr., IMM UrO RAN, 1995, 182–194

[15] Ushakova O.V., “Algorithm of two-dimensional optimal grid generation”, Numerical grid generation in comput. field simulation, Proc. 5th intern. conf., v. 1, eds. B.K. Soni, J.F. Thompson, Mississippi State University, Mississippi State, 1996, 37–46 | MR

[16] Rvachev V.L., Teoriya R-funktsii i nekotorye ee prilozheniya, Naukova dumka, Kiev, 1982 | MR

[17] Gasilova I.A., “Algoritm avtomaticheskogo postroeniya nachalnogo priblizheniya krivolineinoi setki dlya oblastei zvezdnogo tipa”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1994, no. 3, 33–40

[18] Sidorov A.F., “Primery tochnogo postroeniya geometricheski optimalnykh dvumernykh setok”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1994, no. 4, 18–22

[19] Rubina L.I., “Primery tochnogo resheniya zadachi postroeniya trekhmernykh optimalnykh setok”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1995, no. 4, 37–41

[20] Khairullina O.B., “Raschet statsionarnykh dozvukovykh vikhrevykh potokov idealnogo gaza v osesimmetrichnykh kanalakh slozhnykh geometrii”, Voprosy atom. nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 1990, no. 3, 32–39

[21] Akhmadeev V.F., Sidorov A.F., Spiridonov F.F., Khairullina O.B., “O trekh metodakh chislennogo modelirovaniya dozvukovykh techenii v osesimmetrichnykh kanalakh slozhnoi formy”, Modelirovanie v mekhanike, 4 (21):5 (1990), 15–25

[22] Khairullina O.B., “K paschetu vikhrevykh techenii gaza v kanalakh slozhnykh konfiguratsii”, Prikl. mekhanika i tekhn. fizika, 37:2 (1996), 103–108 | Zbl

[23] Khairullina O.B., “Modelling subsonic vortex gas flows in channels of complex geometries”, Russ. J. Numer. Anal. Math. Modelling, 13:3 (1998), 191–219 | DOI | MR

[24] Kokovikhina O.V., Sidorov A.F., Khairullina O.B., “Mathematical modelling of gas-dynamic and acoustic effects in combustion chambers”, Theory of combustion of powder and explosives, ed. A.M. Lipanov, Nova Science, NY, 1996, 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”, Advances in grid generation, ed. O.V. Ushakova, Nova Science, NY, 2007, 337–380 | MR

[26] Koshkina T.N., Sidorov A.F., “Ob odnom geometricheskom sposobe postroeniya trekhmernykh raznostnykh setok”, Chisl. i analit. metody resheniya zadach mekhaniki sploshnoi sredy, cb. tr., Uralskii nauchnyi tsentr, Akademiya nauk SSSR, Sverdlovsk, 1981, 91–100 | MR

[27] Shabashova T.I., “O postroenii optimalnykh krivolineinykh koordinatnykh setok v trekhmernykh oblastyakh”, Chisl. metody mekhaniki sploshnoi sredy, 17:1 (1986), 144–155 | Zbl

[28] Upravlyaemyi termoyadernyi sintez, ed. pod red. Dzh. Killina, Mir, M., 1980

[29] Ushakova O.V., “Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells ”, SIAM J. Sci. Comp, 23:4 (2001), 1289–1273 | DOI | MR

[30] Ushakova O.V., “Usloviya nevyrozhdennosti trekhmernykh yacheek. Formula dlya ob'ema yacheek”, Zhurn. vychisl. matematiki i mat. fiziki, 41:6 (2001), 881–894 | MR | Zbl

[31] Ushakova O.V., “O nevyrozhdennosti trekhmernykh setok”, Tr. In-ta matematiki i mekhaniki UrO RAN, 13:1 (2004), 78–100 | MR

[32] Johnen A., Weill J.C., Remacle J.F., “Robust and efficient validation of the linear hexahedral element”, Procedia Eng., 203 (2017), 271–283 | DOI

[33] Bobylev N.A., Ivanenko S.A., Kazunin A.V., “O kusochno-gladkikh gomeomorfnykh otobrazheniyakh ogranichennykh oblastei i ikh prilozheniyakh k teorii setok”, Zhurn. vychisl. matematiki i mat. fiziki, 43:6 (2003), 808–817 | MR | Zbl

[34] Farin G., Curves and surfaces for computer aided geometric design, A practical guide, Fourth edition, Acad. Press, NY, 1997 | MR | Zbl

[35] Knabner P., Summ G., “The invertibility of the isoparametric mapping for pyramidal and prismatic finite elements”, Numer. Math., 88 (2001), 661–681 | DOI | MR | Zbl

[36] Knabner P., Korotov S., Summ G., “Conditions for the invertibility of the isoparametric mapping for hexahedral finite elements”, Finite. Elem. Anal. Des., 2003 | MR

[37] Vavasis S.A. URL: http://www.cs.cornell.edu/home/vavasis

[38] Bronina T.N., Gasilova I.A., Ushakova O.V., “Algoritmy dlya postroeniya trekhmernykh strukturirovannykh setok”, Zhurn. vychisl. matematiki i mat. fiziki, 43:6 (2003), 875–883 | MR | Zbl

[39] Thompson J.F., Warsi Z.U.A., Mastine C.W., Numerical grid generation: foundation and applications, Elsevier, NY, 1985 | MR

[40] Ushakova O.V., “Klassifikatsiya shestigrannykh yacheek”, Zhurn. vychisl. matematiki i mat. fiziki, 48:8 (2008), 1426–1428

[41] Advanaces in grid generation, ed. O.V. Ushakova, Nova Science, NY, 2007, 430 pp. | MR

[42] Artyomova N.A., Khairullin A.F., Khairullina O.B., “Generation of curvilinear grids in multiply connected domains of complex topology”, Advances in grid generation, ed. O.V. Ushakova, Nova Science, NY, 2007, 161–188 | MR

[43] Martyushov S.N., “Metodika “MODAMS” dlya rascheta zadach obtekaniya metodom konechnykh ob'emov”, Voprosy atom. nauki i tekhniki. Ser. Metodiki i programmy chislennogo resheniya zadach matematicheskoi fiziki, 1998, no. 2, 49–56

[44] Azarenok B.N., “Conservative remapping on hexahedral meshes”, Advances in grid generationed. . O.V. Ushakova, Nova Science, NY, 2007, 337–379 | MR

[45] Azarenok B.N., “Ob odnom metode konservativnoi interpolyatsii na geksaedralnykh setkakh”, Mat. modelirovanie, 20:2 (2008), 59–75 | MR | Zbl

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

[47] Prokhorova M.F., “Problemy gomeomorfizma, voznikayuschie v teorii postroeniya setok”, Tr. In-ta matematiki i mekhaniki UrO RAN, 13:1 (2008), 112–129 | MR

[48] Ushakova O.V., “Nondegeneracy tests for hexahedral cells”, Comput. Methods Appl. Mech. Eng., 200:17–20 (2011), 1649–1658 | DOI | MR | Zbl

[49] Ushakova O.V., “Criteria for hexahedral cell classification”, Appl. Numer. Math., 127 (2018), 18–39 | DOI | MR | Zbl

[50] Bronina T.N., “Algoritm postroeniya nachalnykh trekhmernykh strukturirovannykh setok dlya oblastei vrascheniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14:1 (2008), 3–10 | MR

[51] Ushakova O.V., “Algoritmy optimizatsii trekhmernykh setok dlya oblastei vrascheniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14:1 (2008), 150–180

[52] Godunov C.K., Zabrodin A.V., Ivanov M.Ya., Kraiko A.N., Prokopov G.P., Chislennoe reshenie mnogomernykh zadach gazovoi dinamiki, Nauka, M., 1976, 400 pp. | MR

[53] Knupp P.M., Steinberg S., Fundamentals of grid generation, CRC Press, Boca Raton, FL, 1994 | MR | Zbl

[54] Liseikin V.D., Grid generation methods, Springer, Berlin, 1999 | MR | Zbl

[55] Kurant R., Uravneniya s chastnymi proizvodnymi, Mir, M., 1964

[56] Sidorov A.F., Shabashova T.I., “Ob odnom metode rascheta optimalnykh raznostnykh setok dlya mnogomernykh oblastei”, Chisl. metody mekhaniki sploshnoi sredy, 12:5 (1981), 106–123

[57] Ushakova O.V., “Teorema suschestvovaniya i edinstvennosti resheniya kraevoi zadachi postroeniya odnomernykh optimalnykh adaptiruyuschikhsya setok”, Modelirovanie v mekhanike, 3:2 (1989), 134–141 | MR | Zbl

[58] Ivanenko C.A., Charakhchyan A.A., “Krivolineinye setki iz vypuklykh chetyrekhugolnikov”, Zhurn. vychisl. matematiki i mat. fiziki, 28:4 (1988), 503–514

[59] Ivanenko S.A., Selected chapters on grid generation and applications, Dorodnicyn Computing Centre of the Russian Academy of Sciences, M., 2004 | MR | Zbl

[60] Dobrev V., Knupp P., Kolev T., Mittal K., Tomov V., “hr-Adaptivity for nonconforming high-order meshes with the target matrix optimization paradigm”, Eng. Comput., 38 (2022), 3721–3737 | DOI

[61] Dobrev V., Knupp P., Kolev T., Mittal K., Tomov V., “The target-matrix optimization paradigm for high-order meshes”, SIAM J. Sci. Comput., 1 (2019), B50–B68 | DOI | MR | Zbl

[62] Mittal K., Fischer P., “Mesh smoothing for the spectral element method”, J. Sci. Comput., 78 (2019), 1152–1173 | DOI | MR | Zbl

[63] Turner M., Peiro J., Moxey D., “Curvilinear mesh generation using a variational framework”, Comput.-Aided Des., 103 (2018), 73–91 | DOI | MR

[64] Xu K., Gao X., Chen G., “Hexahedral mesh quality improvement via edge-angle optimization”, Comput. Graph., 70 (2018), 17–27 | DOI

[65] Zhu Y., Bridson R., Kaufman D.M., “Blended cured quasi-newton for distortion optimization”, ACM Trans. Graph., 37:4 (2018) | DOI

[66] Ushakova O.V., “Algoritm korrektsii setki k oblasti vrascheniya”, Vopr. atomnoi nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 2016, no. 1, 16–27

[67] Ushakova O.V., “Primenenie algoritma korrektsii setki k oblasti vrascheniya”, Vopr. atomnoi nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 2016, no. 2, 31–37

[68] Ushakova O.V., Artyomova N.A., Bronina T.N., Anuchina A.I., Gordeichuk V.I., “Grid generation in deformed volumes of revolution”, Proc. Internat. conf. “Advanced mathematics, computations and applications 2015” (AMCA-2015), dedicated to the 90th anniversary of the birthday of academician Marchuk G.I. (Instit. Comp. Mathematics and Math. Geophysics SB RAS, Akademgorodok), Abvey, Novosibirsk, 2015, 782–788

[69] Zegeling P.A., “Moving grid techniques”, Handbook of grid generation, eds. J.F. Thompson, B.K. Soni, N.P. Weatheril, CRC Press, Boca Raton; London; NY; Washington, 1999, 37, 22 pp. | MR

[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”, Proc. of the 20th Internat. meshing roundtable, ed. W.R. Quadros, Springer, Berlin; Heidelberg, 2011, 293–311 | DOI

[71] Immonen E., “A parametric morphing method for generating structured meshes for marine free surface flow applications with plane symmetry”, J. Comput. Des. Eng., 6 (2019), 348–353 | DOI

[72] Biancolini M.E., Chiappa A., Giorgetti F., Porziania S., Rochette M., “Radial basis functions mesh morphing for the analysis of cracks propagation”, Procedia Struct. Integr., 8 (2018), 433–443 | DOI

[73] Prokopov G. P., “Moving mesh calculation in unsteady two-dimensional problems”, Advances in grid generation, ed. O.V. Ushakova, Nova Science, NY, 2007, 127–160 | MR

[74] Artemova N.A., “Nestatsionarnyi algoritm postroeniya strukturirovannykh setok v deformirovannykh oblastyakh”, Vopr. atomnoi nauki i tekhniki. Cer. Mat. modelirovanie fiz. protsessov, 2018, no. 4, 76–86

[75] Ushakova O.V., “Algoritm korrektsii setki k oblasti, obrazovannoi poverkhnostyami vrascheniya s parallelnymi osyami vrascheniya”, Vopr. atomnoi nauki i tekhniki. Cer. Mat. modelirovanie fiz. protsessov, 2018, no. 1, 30–41

[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”, Numerical geometry, grid generation and scientific computing, Proc. of the 9th international conference ( NUMGRID 2018 / Voronoi 150, Celebrating the 150th anniversary of G.F. Voronoi), Lect. Notes Comput. Sci. Eng., 131, eds. V.A. Garanzha, L. Kamenski, H. Si, 2019, 281–292 | DOI | MR | Zbl

[77] Artemova N.A., Ushakova O.V., “O razvitii algoritma postroeniya setok v deformirovannykh telakh vrascheniya dlya sluchaya ikh deformatsii telami vrascheniya, obrazovannymi neskolkimi poverkhnostyami”, Vopr. atomnoi nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 2020, no. 4, 86–96 | MR

[78] Ushakova O.V., “Algoritm korrektsii setki k deformirovannoi oblasti vrascheniya”, Vopr. atomnoi nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 2017, no. 2, 53–65

[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”, J. Phys. Conf. Ser., 1392 (2019), 012029 | DOI | MR

[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 Conf. Proc., 2312 (2020), 050002 | DOI

[81] Artyomova N.A., Ushakova O.V., “About grid generation in constructions bounded by the surfaces of revolution”, J. Phys. Conf. Ser., 2099 (2021), 012018 | DOI

[82] Ushakova O.V., Artyomova N.A., “Non-stationary grid generation algorithm for deformed volumes of revolution”, Mathematics and Computers in Simulation, 203 (2023), 878–909 | DOI | MR

[83] Ushakova O.V., “Realizatsiya kriteriya adaptatsii v tekhnologii postroeniya setok dlya konstruktsii, ogranichennykh poverkhnostyami vrascheniya s parallelnymi osyami vrascheniya”, Sib. zhurn. vychisl. matematiki, 2023, no. 1, 93–100 | DOI

[84] Ushakova O.V., Artemova N.A., “Tekhnologii postroeniya setok v konstruktsiyakh, ogranichennykh poverkhnostyami vrascheniya s parallelnymi osyami vrascheniya”, Vestn. Bashkirsk. un-ta, 27:3 (2022), 541–546 | DOI

[85] Ushakova O.V., “Realizatsii kriteriya adaptatsii v algoritme postroeniya optimalnykh setok”, Vopr. atomnoi nauki i tekhniki. Ser. Mat. modelirovanie fiz. protsessov, 2021, no. 2, 80–95

[86] Liseikin V.D., “Obzor metodov postroeniya strukturirovannykh adaptivnykh setok”, Zhurn. vychisl. matematiki i mat. fiziki, 36:1 (1996), 3–41 | MR | Zbl