MULTIGRID METHODS WITH SKEW-HERMITIAN BASED SMOOTHERS FOR THE CONVECTION-DIFFUSION PROBLEM WITH DOMINANT CONVECTION (2022)
The convection-diffusion equation with dominant convection is considered on a uniform grid of central difference scheme. The multigrid method is used for solving the strongly nonsymmetric systems of linear algebraic equations with positive definite coefficient matrices. Two-step skew-Hermitian iterative methods are utilized for the first time as a smoothing procedure. It is demonstrated that using the proper smoothers enables to improve the convergence of the multigrid method. The robustness of the smoothers with respect to variation of the Peclet number is shown by local Fourier analysis and numerical experiments.
Идентификаторы и классификаторы
The need to solve the convection–diffusion equation arises in the mathematical modeling of a great number of real processes. Especially many problems appear when the highest derivative has a small parameter. Various approaches for solving this problem are proposed. They are related to both different approximation methods of convective terms, which significantly affect the properties of the resulting nonsymmetric matrix, and the construction of special grids [1–4]. Moreover, this class of problems is a test one when studying the convergence of iteration methods for solving non-self-adjoint systems of linear equations.
Список литературы
- G. Birkhoff, E. C. Gartland Jr., and R. E. Lynch, “Difference Methods for Solving Convection-Diffusion Equations”, Comput. Math. Appl. 19 (11), 147-160 (1990). DOI: 10.1016/0898-1221(90)90158-G EDN: YKNXMY
- P. N. Vabishchevich and A. A. Samarskii, “Finite Difference Schemes for Convection-Diffusion Problems on Irregular Meshes”, Comput. Math. Math. Phys. 40 (5), 692-704 (2000). EDN: LGHULJ
- J. Zhang, “Preconditioned Iterative Methods and Finite Difference Schemes for Convection-Diffusion”, Appl. Math. Comput. 109 (1), 11-30 (2000). DOI: 10.1016/S0096-3003(99)00013-2 EDN: AEJFEH
- T. Ma, L. Zhang, F. Cao, and Y. Ge, “A Special Multigrid Strategy on Non-Uniform Grids for Solving 3D Convection-Diffusion Problems with Boundary/Interior Layers”, Symmetry, 13 (7), (2021). DOI: 10.3390/sym13071123
- V. V. Voevodin and Yu. A. Kuznetsov, Matrices and Computations (Nauka, Moscow, 1984) [in Russian].
- L. A. Krukier, “Implicit Difference Schemes and an Iteration Method for Their Solution for a Class of Systems of Quasilinear Equations”, Sov. Math. 23 (7), 43-51 (1979).
- L. A. Krukier, “Convergence Acceleration of Triangular Iterative Methods Based on the Skew-Symmetric Part of the Matrix”, Appl. Numer. Math., 30 (2-3), 281-290 (1999). DOI: 10.1016/S0168-9274(98)00116-0 EDN: LFIVDV
- Z.-Z. Bai, L. A. Krukier, and T. S. Martynova, “Two-Step Iterative Methods for Solving the Stationary Convection-Diffusion Equation with a Small Parameter at the Highest Derivative on a Uniform Grid”, Comput. Math. Math. Phys. 46 (2), 282-293 (2006). DOI: 10.1134/S0965542506020102 EDN: LJUTBT
- L. A. Krukier, T. S. Martynova, and Z.-Z. Bai, “Product-Type Skew-Hermitian Triangular Splitting Iteration Methods for Strongly Non-Hermitian Positive Definite Linear Systems”, J. Comput. Appl. Math. 232 (1), 3-16, (2009). DOI: 10.1016/j.cam.2008.10.033 EDN: LLPYLH
-
G. Muratova and E. Andreeva, "Multigrid Method for Fluid Dynamics Problems", J. Comput. Math. 32 (3), 233-247 (2014). DOI: 10.4208/JCM.1403-CR11 EDN: UGPUXF -
R. P. Fedorenko, "A Relaxation Method for Solving Elliptic Difference Equations", USSR Comput. Math. Math. Phys. 1 (4), 1092-1096 (1962). DOI: 10.1016/0041-5553(62)90031-9 EDN: AIVTGH -
A. Brandt, "Multi-Level Adaptive Solutions to Boundary-Value Problems", Math. Comput. 31, 333-390 (1977). DOI: 10.1090/S0025-5718-1977-0431719-X -
U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid (Academic Press, London, 2001). -
P. Wesseling and C. W. Oosterlee, "Geometric Multigrid with Applications to Computational Fluid Dynamics", J. Comput. Appl. Math. 128 (1-2), 311-334 (2001). DOI: 10.1016/S0377-0427(00)00517-3 EDN: YJGRMY -
V. T. Zhukov, N. D. Novikova, and O. B. Feodoritova, "Multigrid Method for Elliptic Equations with Anisotropic Discontinuous Coefficients", Comput. Math. Math. Phys. 55 (7), 1150-1163 (2015). DOI: 10.1134/S0965542515070131 EDN: UFBOWH -
Y. Pan and P.-O. Persson, "Agglomeration-Based Geometric Multigrid Solvers for Compact Discontinuous Galerkin Discretizations on Unstructured Meshes", J. Comput. Phys. 449 (2021). DOI: 10.1016/j.jcp.2021.110775 EDN: LIUWJN -
S. Dargaville, A. G. Buchan, R. P. Smedley-Stevenson, et al., "A Comparison of Element Agglomeration Algorithms for Unstructured Geometric Multigrid", J. Comput. Appl. Math. 390 (2021). DOI: 10.1016/j.cam.2020.113379 -
W. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial (SIAM Press, Philadelphia, 2000). -
K. Stüben, "Algebraic Multigrid (AMG): Experiences and Comparisons", Appl. Math. Comput. 13 (3-4), 419-451 (1983). DOI: 10.1016/0096-3003(83)90023-1 -
R. D. Falgout, "An Introduction to Algebraic Multigrid", Comput. Sci. Eng. 8 (6), 24-33 (2006). DOI: 10.1109/MCSE.2006.105 -
S. I. Martynenko, "Numerical Methods for Black Box Software", Vychisl. Metody Program. 20, 147-169 (2019). DOI: 10.26089/NumMet.v20r215 EDN: IJJQNL -
U. M. Yang, "Parallel Algebraic Multigrid Methods - High Performance Preconditioners", in Lecture Notes in Computational Science and Engineering (Springer, Heidelberg, 2006), Vol. 51, pp. 209-236. DOI: 10.1007/3-540-31619-1_6 -
H. Sterck, U. M. Yang, and J. J. Heys, "Reducing Complexity in Parallel Algebraic Multigrid Preconditioners", SIAM J. Matrix Anal. Appl. 27 (4), 1019-1039 (2006). DOI: 10.1137/040615729 -
G. Muratova, T. Martynova, E. Andreeva, et al., "Numerical Solution of the Navier-Stokes Equations Using Multigrid Methods with HSS-Based and STS-Based Smoothers", Symmetry 12 (2020). DOI: 10.3390/sym12020233 EDN: KCUDAZ -
Sh. Li and Zh. Huang, "Convergence Analysis of HSS-Multigrid Methods for Second-Order Nonselfadjoint Elliptic Problems", BIT Numer. Math. 53 (4), 987-1012 (2013). DOI: 10.1007/S10543-013-0433-5 -
S. Hamilton, M. Benzi, and E. Haber, "New Multigrid Smoothers for the Oseen Problems", Numer. Linear Algebra Appl. 17 (2-3), 557-576 (2010). DOI: 10.1002/nla.707 EDN: NAHZSV -
Y. He and S. P. MacLachlan, "Local Fourier Analysis of Block-Structured Multigrid Relaxation Schemes for the Stokes Equations", Numer. Linear Algebra Appl. 25 (3), 1-28, (2018). DOI: 10.1002/nla.2147 EDN: VERGWO -
M. S. Darwish, T. Saad, and Z. Hamdan, "A High Scalability Parallel Algebraic Multigrid Solver", in Proc. European Conf. on Computational Fluid Dynamics (ECCOMAS CFD 2006), Egmond aan Zee, Netherlands, September 5-8, 2006. DOI: 10.1007/978-3-540-92779-2_34 -
L. Wang and Z.-Z. Bai, "Skew-Hermitian Triangular Splitting Iteration Methods for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts", BIT Numer. Math. 44, 363-386 (2004). DOI 10.1023/B: BITN.0000039428.54019.15. EDN: MCTULF -
Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM Press, Philadelphia, 2003). -
M. A. Botchev and L. A. Krukier, "Iteration Solution of Strongly Nonsymmetric Systems of Linear Algebraic Equations", Comput. Math. Math. Phys. 37 (11), 1241-1251 (1997). -
L. A. Krukier, "Iterative Solution of Nonsymmetric Linear Equation Systems with Dominant Skew-Symmetric Part", in Proc. Int. Summer School on Iterative Methods and Matrix Computation, Rostov-on-Don, Russia, June 2-9, 2002 (Rostov State Univ., Rostov-on-Don, 2002), pp. 205-259. -
J. H. Bramble, J. E. Pasciak, and J. C. Xu, "The Analysis of Multigrid Algorithms for Nonsymmetric and Indefinite Elliptic Problems", Math. Comput. 51, 389-414 (1988). DOI: 10.1090/S0025-5718-1988-0930228-6 -
Z.-H. Cao, "Convergence of Multigrid Methods for Nonsymmetric, Indefinite Problems", Appl. Math. Comput. 28 (4), 269-288 (1988). DOI: 10.1016/0096-3003(88)90076-8 -
J. Mandel, "Multigrid Convergence for Nonsymmetric, Indefinite Variational Problems and One Smoothing Step", Appl. Math. Comput. 19 (1-4), 201-216 (1986). DOI: 10.1016/0096-3003(86)90104-9
Выпуск
Методы и алгоритмы вычислительной математики и их приложения.
Параллельные программные средства и технологии.
Другие статьи выпуска
Рассмотрены подходы к моделированию многофазных потоков в нефтяном коллекторе при фиксировании рабочего давления на зонах перфорации активных скважин. Предложенный численный метод основан на неявном расчете давления и явном пересчете насыщенностей фаз в ячейках сетки на каждом временн´ом шаге. Представлено описание математической модели, общей вычислительной схемы, конечноэлементной аппроксимации поля давления. Для сохранения консервативности потоков смеси используется специальный метод балансировки, приводится его алгоритм. Проведены исследования на задаче сравнительного проекта SPE-10, для которой расчет потоков на зонах перфорации скважин при фиксированном давлении выполнялся с использованием двух подходов.
В работе рассматривается численная реализация метода обращения полного волнового поля на основе асимптотического решения уравнения Гельмгольца. Классическая постановка задачи заключается в поиске минимума штрафной функции, характеризующей среднеквадратичное уклонение модельных данных от зарегистрированных при проведении полевых работ. Для минимизации целевого функционала обычно применяются методы локальной оптимизации, такие как метод сопряженных градиентов. Именно вычисление градиента штрафной функции и является самой ресурсоемкой частью задачи. Асимптотический подход к решению обратной динамической задачи сейсмики заключается в замене дорогостоящей конечно-разностной процедуры расчета функции Грина краевой задачи частотно-зависимым лучевым трассированием. Функции Грина рассчитываются на основании данных о времени пробега вдоль лучей, об амплитуде и о геометрическом расхождении. Серия численных экспериментов для широкоизвестной модели Marmousi демонстрирует эффективность применения такого подхода к реконструкции макроскоростного строения сложноустроенных сред для низких временных частот. При сопоставимом качестве решения обратной задачи применительно к стандартному конечно-разностному подходу скорость расчетов асимптотического метода на порядок выше.
Рассматриваются программы, выполняемые на видеокартах общего назначения и представленные в виде “ядер”, не содержащих циклов с неопределенной продолжительностью. Такие ядра могут быть реализованы, например, с помощью технологий CUDA или OpenCL. Для оценки времени работы подобных программ предложены модели их работы: от совсем “наивной” до более реалистичных. Все они формулируются как матричные выражения в max-plus-алгебре.
Ранее в наших работах было предложено в задачах веерной томографии применять методы перевода пучка веерных лучей в набор параллельных лучей. Это достигалось специальной деформацией искомой томограммы на этапе обратного проецирования измеренных и отфильтрованных проекций, с последующей операцией обратной деформации. Деформация томограммы для каждого направления наблюдения будет своя, но взаимно-однозначный характер этих деформаций позволяет вернуться к исходной системе координат. В данной работе этот метод обобщен на семейство плоских криволинейных траекторий, позволяющих взаимно-однозначные переходы к параллельным лучам. Для каждой обратной проекции изображение оказывается промодулировано известной функцией, следующей из уравнения дифференциала пути заданной траектории. Результаты обобщения широко распространенного в методах двумерной томографии алгоритма FBP демонстрируются на примерах параболической, синусоидальной и веерной траекторий лучей.
Издательство
- Издательство
- МГУ
- Регион
- Россия, Москва
- Почтовый адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- Юр. адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- ФИО
- Садовничий Виктор Антонович (РЕКТОР)
- E-mail адрес
- info@rector.msu.ru
- Контактный телефон
- +7 (495) 9391000
- Сайт
- https://msu.ru/