УДК 519.6
MSC: 35-04, 65M50, 65M06
DOI: 10.21538/0134-4889-2023-29-2-217-247
Полный текст статьи (Full text)
В статье представлен обзор более полувекового развития вариационного подхода построения оптимальных сеток, предложенного А.Ф. Сидоровым. Изложены концепция подхода, основу которой в качестве критериев оптимальности сеток составляют требования близости сетки к равномерной, ортогональной и адаптации к заданной функции или решению уравнений в частных производных, и ее применение для построения структурированных сеток в двумерных и трехмерных областях геометрически сложной формы. Описываются созданные алгоритмы построения сеток и их приложения. Обзор поделен на два периода: годы жизни ученого и последующие годы. Конструкции функционалов, формализующих критерии оптимальности сеток, изложены применительно к единой технологии построения сеток, созданной во второй период для численного моделирования вихревых процессов многокомпонентной гидродинамики. Приводятся примеры расчетов сеток по развиваемому в настоящее время в рамках указанной технологии алгоритму построения сеток в объемах, полученных деформациями объемов вращения с помощью обобщений объемов вращения. Под объемом вращения понимается конструкция, образованная вращением плоской образующей кривой, состоящей из отрезков прямых, дуг окружностей и эллипсов, называемых элементами, на 180∘ вокруг оси. Обобщение объема вращения представляет собой объем, образованный поверхностями, полученными вращением элементов плоских образующих кривых на 180∘ вокруг параллельных осей. Деформированный объем вращения представляет собой объем, полученный деформацией объема вращения другим объемом вращения или его обобщением. Случаи объемов вращения, обобщений объемов вращения, объемов вращения, деформированных объемами вращения, сформировали описываемую технологию построения сеток. Базовой конструкцией в технологии является объем вращения, позволивший осуществлять ее дальнейшее развитие в направлении усложнения конструкций. В настоящее время возможно строить структурированные сетки в очень сложных трехмерных областях. Такая возможность появилась благодаря применению техники подвижных сеток, естественным образом реализуемой в вариационных конструкциях, и разработки нестационарного алгоритма, осуществляющего деформацию объема вращения до нужной деформированной формы, деформацию и оптимизацию сетки с целью удовлетворения критериев оптимальности.
Ключевые слова: структурированные сетки, оптимальные сетки, подвижные сетки, построение сеток в деформированных областях
СПИСОК ЛИТЕРАТУРЫ
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. 1989. Vol. 4, № 2. P. 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 // Handbook of grid generation / eds. J.F. Thompson, B.K. Soni, N.P. Weatherill. Boca Raton; London; NY; Washington: CRC Press, 1999. P. 36-1–36-25.
3. Сидоров А.Ф. Об одном алгоритме расчета оптимальных разностных сеток // Тр. Математического ин-та им. В.А.Стеклова АН СССР. 1966. Т. 74. С. 147–151.
4. Потугина И.В. Освоение и развитие методики программ расчета одномерных задач энерговыделения во ВНИИЭФ (1954–1986) // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1998. Вып. 2. С. 50–59.
5. Широковская О.С. Замечание к статье А.Ф. Сидорова “Об одном алгоритме расчета оптимальных разностных сеток” // Журн. вычисл. математики и мат. физики. 1969. Т. 9, № 2. С. 468–469.
6. Тихонов А.Н., Самарский А.А. Однородные разностные схемы на неравномерных сетках // Журн. вычисл. математики и мат. физики. 1985. Т. 2, № 5. C. 812–832.
7. Емельянов К.В. Применение оптимальных разностных сеток к решению задач с сингулярным возмущением // Журн. вычисл. математики и мат. физики. 1994. Т. 34, № 6. С. 936–943.
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. 1995. Vol. 10, № 4. P. 299–310.
9. Сидоров А.Ф. Об одном алгоритме расчета криволинейных сеток, близких к равномерным // Числ. методы механики сплошной среды. 1977. Т. 8, № 4. С. 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. 1996. Vol. 11, no. 4. P. 343–358.
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. Mississippi State: ISGG, 1998. P. 759–769.
12. Артемова Н.А., Хайруллин А.Ф., Хайруллина О.Б. Параллельный алгоритм расчета оптимальных сеток // Вычисл. технологии. 2001. Т. 6, № 2. С. 3–13.
13. Ушакова О.В. ЛАДА — экономичный алгоритм и программа построения двумерных криволинейных оптимальных адаптивных сеток в односвязных областях геометрически сложной формы // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1994. Вып. 3. С. 47–56.
14. Ушакова О.В. Параллельный алгоритм и программа построения оптимальных адаптивных сеток // Алгоритмы и програм. средства парал. вычислений: сб. науч. тр. / ИММ УрО РАН. 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. / eds. B.K. Soni, J.F. Thompson. Mississippi State: Mississippi State University, 1996. Vol. 1. P. 37–46.
16. Рвачев В.Л. Теория R-функций и некоторые ее приложения. Киев: Наукова думка, 1982.
17. Гасилова И.А. Алгоритм автоматического построения начального приближения криволинейной сетки для областей звездного типа // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1994. Вып. 3. С. 33–40.
18. Сидоров А.Ф. Примеры точного построения геометрически оптимальных двумерных сеток // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1994. Вып. 4. С. 18–22.
19. Рубина Л.И. Примеры точного решения задачи построения трехмерных оптимальных сеток // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1995. Вып. 4. С. 37–41.
20. Хайруллина О.Б. Расчет стационарных дозвуковых вихревых потоков идеального газа в осесимметричных каналах сложных геометрий // Вопросы атом. науки и техники. Сер. Мат. моделирование физ. процессов. 1990. Вып. 3. С. 32–39.
21. Ахмадеев В.Ф., Сидоров А.Ф., Спиридонов Ф.Ф., Хайруллина О.Б. О трех методах численного моделирования дозвуковых течений в осесимметричных каналах сложной формы // Моделирование в механике. 1990. Т. 4 (21), № 5. С. 15–25.
22. Хайруллина О.Б. К pасчету вихревых течений газа в каналах сложных конфигураций // Прикл. механика и техн. физика. 1996. Т. 37, № 2. С. 103–108.
23. Khairullina O.B. Modelling subsonic vortex gas flows in channels of complex geometries // Russ. J. Numer. Anal. Math. Modelling. Vol. 13, no. 3. 1998. P. 191–219.
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. NY: Nova Science, 1996. P. 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. NY: Nova Science, 2007. P. 337–380.
26. Кошкина Т.Н., Сидоров А.Ф. Об одном геометрическом способе построения трехмерных разностных сеток // Числ. и аналит. методы решения задач механики сплошной среды: cб. тр. Свердловск: Уральский научный центр, Академия наук СССР, 1981. С. 91–100.
27. Шабашова Т.И. О построении оптимальных криволинейных координатных сеток в трехмерных областях // Числ. методы механики сплошной среды. 1986. Т. 17, № 1. С. 144–155.
28. Управляемый термоядерный синтез / под ред. Дж. Киллина. М.: Мир. 1980.
29. Ushakova O.V. Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells // SIAM J. Sci. Comp. 2001. Vol. 23, iss. 4. P. 1289–1273.
30. Ушакова О.В. Условия невырожденности трехмерных ячеек. Формула для объема ячеек // Журн. вычисл. математики и мат. физики. 2001. T. 41, № 6. С. 881–894.
31. Ушакова О.В. О невырожденности трехмерных сеток // Тр. Ин-та математики и механики УрО РАН. 2004. Т. 13, № 1. C. 78–100.
32. Johnen A., Weill J.C., Remacle J.F. Robust and efficient validation of the linear hexahedral element // Procedia Eng. 2017. Vol. 203. P. 271–283.
33. Бобылев Н.А., Иваненко С.А., Казунин А.В. О кусочно-гладких гомеоморфных отображениях ограниченных областей и их приложениях к теории сеток // Журн. вычисл. математики и мат. физики. 2003. Т. 43, № 6. C. 808–817.
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 // Numer. Math. 2001. Vol. 88. P. 661–681.
36. Knabner P., Korotov S., Summ G. Conditions for the invertibility of the isoparametric mapping for hexahedral finite elements // Finite. Elem. Anal. Des. 2003.
37. Vavasis S.A. A Bernstein–Bezier sufficient condition for invertibility of polynomial mapping functions: e-resource (November 3, 2001). URL: http://www.cs.cornell.edu/home/vavasis .
38. Бронина Т.Н., Гасилова И.А., Ушакова О.В. Алгоритмы для построения трехмерных структурированных сеток // Журн. вычисл. математики и мат. физики. 2003. T. 43, № 6. C. 875–883.
39. Thompson J.F., Warsi Z.U.A., Mastine C.W. Numerical grid generation: foundation and applications. NY: Elsevier, 1985.
40. Ушакова О.В. Классификация шестигранных ячеек // Журн. вычисл. математики и мат. физики. 2008. Т. 48, № 8. С. 1426–1428.
41. Advanaces in grid generation / ed. O.V. Ushakova. NY: Nova Science, 2007. 430 p.
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. NY: Nova Science, 2007. P. 161–188.
43. Мартюшов С.Н. Методика “МОДАМС” для расчета задач обтекания методом конечных объемов // Вопросы атом. науки и техники. Сер. Методики и программы численного решения задач математической физики. 1998. Вып. 2. С. 49–56.
44. Azarenok B.N. Conservative remapping on hexahedral meshes // Advances in grid generation / ed. O.V. Ushakova. NY: Nova Science, 2007. P. 337–379.
45. Азаренок Б.Н. Об одном методе консервативной интерполяции на гексаэдральных сетках // Мат. моделирование. 2008. Т. 20, № 2. С. 59–75.
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. Прохорова М.Ф. Проблемы гомеоморфизма, возникающие в теории построения сеток // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 13, № 1. C. 112–129.
48. Ushakova O.V. Nondegeneracy tests for hexahedral cells // Comput. Methods Appl. Mech. Eng. 2011. Vol. 200, iss. 17–20. P. 1649–1658.
49. Ushakova O.V. Criteria for hexahedral cell classification // Appl. Numer. Math. 2018. Vol. 127. P. 18–39. doi: 10.1016/j.apnum.2017.12.012 .
50. Бронина Т.Н. Алгоритм построения начальных трехмерных структурированных сеток для областей вращения // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, № 1. C. 3–10.
51. Ушакова О.В. Алгоритмы оптимизации трехмерных сеток для областей вращения // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, № 1. С. 150–180.
52. Годунов C.K., Забродин А.В., Иванов М.Я., Крайко А.Н., Прокопов Г.П. Численное решение многомерных задач газовой динамики. М.: Наука, 1976. 400 с.
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. Kурант Р. Уравнения с частными производными. М.: Мир, 1964.
56. Сидоров А.Ф., Шабашова Т.И. Об одном методе расчета оптимальных разностных сеток для многомерных областей // Числ. методы механики сплошной среды. 1981. Т. 12, № 5. C. 106–123.
57. Ушакова О.В. Теорема существования и единственности решения краевой задачи построения одномерных оптимальных адаптирующихся сеток // Моделирование в механике. 1989. Т. 3, № 2. С. 134–141.
58. Иваненко C.A., Чарахчьян А.А. Криволинейные сетки из выпуклых четырехугольников // Журн. вычисл. математики и мат. физики. 1988. Т. 28, № 4. С. 503–514.
59. Ivanenko S.A. Selected chapters on grid generation and applications. M.: Dorodnicyn Computing Centre of the Russian Academy of Sciences, 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 // Eng. Comput. 2022. Vol. 38. P. 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 J. Sci. Comput. 2019. Vol. 1. P. B50–B68. doi: 10.1137/18M1167206
62. Mittal K., Fischer P. Mesh smoothing for the spectral element method // J. Sci. Comput. 2019. Vol. 78. P. 1152–1173. doi: 10.1007/s10915-018-0812-9
63. Turner M., Peiro J., Moxey D. Curvilinear mesh generation using a variational framework // Comput.-Aided Des. 2018. Vol. 103. P. 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 // Comput. Graph. 2018. Vol. 70. P. 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 Trans. Graph. 2018. Vol. 37, № 4. doi: 10.1145/3197517.3201359
66. Ушакова О.В. Алгоритм коррекции сетки к области вращения // Вопр. атомной науки и техники. Сер. Мат. моделирование физ. процессов. 2016. Вып. 1. С. 16–27.
67. Ушакова О.В. Применение алгоритма коррекции сетки к области вращения // Вопр. атомной науки и техники. Сер. Мат. моделирование физ. процессов. 2016. Вып. 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. Novosibirsk: Abvey, 2015. P. 782–788.
69. Zegeling P.A. Moving grid techniques // Handbook of grid generation / eds. J.F. Thompson, B.K. Soni, N.P. Weatheril. Boca Raton; London; NY; Washington: CRC Press, 1999. P. 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 // Proc. of the 20th Internat. meshing roundtable / ed. W.R. Quadros. Berlin; Heidelberg: Springer, 2011. P. 293–311.
71. Immonen E. A parametric morphing method for generating structured meshes for marine free surface flow applications with plane symmetry // J. Comput. Des. Eng. 2019. Vol. 6. P. 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 Struct. Integr. 2018. Vol. 8. P. 433–443.
73. Prokopov G. P. Moving mesh calculation in unsteady two-dimensional problems // Advances in grid generation / ed. O.V. Ushakova. NY: Nova Science, 2007. P. 127–160.
74. Артемова Н.А. Нестационарный алгоритм построения структурированных сеток в деформированных областях // Вопр. атомной науки и техники. Cер. Мат. моделирование физ. процессов. 2018. Вып. 4. С. 76–86.
75. Ушакова О.В. Алгоритм коррекции сетки к области, образованной поверхностями вращения с параллельными осями вращения // Вопр. атомной науки и техники. Cер. Мат. моделирование физ. процессов. 2018. Вып. 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) / eds. V.A. Garanzha, L. Kamenski, H. Si. Ser. Lect. Notes Comput. Sci. Eng. 2019. Vol. 131. P. 281–292.
77. Артемова Н.А., Ушакова О.В. О развитии алгоритма построения сеток в деформированных телах вращения для случая их деформации телами вращения, образованными несколькими поверхностями // Вопр. атомной науки и техники. Сер. Мат. моделирование физ. процессов. 2020. Вып. 4. С. 86–96.
78. Ушакова О.В. Алгоритм коррекции сетки к деформированной области вращения // Вопр. атомной науки и техники. Сер. Мат. моделирование физ. процессов. 2017. Вып. 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. 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 Conf. Proc. 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 // J. Phys. Conf. Ser. 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. P. 878–909. doi: 10.1016/j.matcom.2022.07.016
83. Ушакова О.В. Реализация критерия адаптации в технологии построения сеток для конструкций, ограниченных поверхностями вращения с параллельными осями вращения // Сиб. журн. вычисл. математики. 2023. № 1. C. 93–100. doi: 10.15372/SJNM20230107
84. Ушакова О.В., Артемова Н.А. Технологии построения сеток в конструкциях, ограниченных поверхностями вращения с параллельными осями вращения // Вестн. Башкирск. ун-та. 2022. Т. 27, № 3. С. 541–546. doi: 10.33184/bulletin-bsu-2022.3.9
85. Ушакова О.В. Реализации критерия адаптации в алгоритме построения оптимальных сеток // Вопр. атомной науки и техники. Сер. Мат. моделирование физ. процессов. 2021. Вып. 2. С. 80–95.
86. Лисейкин В.Д. Обзор методов построения структурированных адаптивных сеток // Журн. вычисл. математики и мат. физики. 1996. T. 36, № 1. C. 3–41.
Поступила 1.03.2023
После доработки 13.03.2023
Принята к публикации 20.03.2023
Ушакова Ольга Васильевна
д-р физ.-мат., наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
Уральский федеральный университет
г. Екатеринбург
e-mail: uov@imm.uran.ru
Ссылка на статью: О.В. Ушакова. O развитии вариационного подхода построения оптимальных сеток (обзор) // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 2. С. 217-247
English
O.V. Ushakova. On the development of the variational approach to the generation of optimal grids (a survey)
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
Received March 1, 2023
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
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]
