MULTIGRID METHODS OF MACRO-GRID DOMAIN DECOMPOSITION

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We consider integrated multigrid domain decomposition methods (DDM-MG) for solving large systems of linear algebraic equations (SLAEs) with sparse symmetric or asymmetric matrices and multivariate boundary value problems obtained by grid approximations. The proposed algorithms are based on the construction of single-layer or two-layer macrogrids and special ordering of nodes according to their belonging to different topological primitives of the macrogrid: macro nodes, macro edges, macro faces and subareas. At coordinated numbering of vector components, the SLAU matrix in the three-dimensional case takes a block-tri-diagonal form of the fourth order. For its solution we use some method of approximate filtering in Krylov subspaces. At the same time, the solution of auxiliary systems in subspaces is carried out by multigrid methods of block incomplete factorization, on the basis of similar topology-oriented ordering of nodes, but not at the macro-, but at the micro-level, resulting in the formation of a single preconditioner of recursive-nested type. The justification of the proposed methods is carried out for Stiltjes-type matrices.

About the authors

V. P Ilyin

Institute of Computational Mathematics and Mathematical Geophysics SB RAS

Email: ilin@sscc.ru
Novosibirsk Russia

References

  1. Dolean V., Jolivet P., Nataf F. An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation, SIAM, Philadelphia, 2015.
  2. Laevsky Y.M., Matsokin A.M. Decomposition Methods for Solving Elliptic and Parabolic Boundary Value Problems // Sib. Zh. Ind. Math. 1992. P. 361–372.
  3. Vassilevski Y., Olshanskii M.A. Short Course on Multi-Grid and Domain Decomposition Methods. MAKS, Moscow, 2007.
  4. Notay Y. Algebraic Multigrid for Stokes Equations // SIAM J. Sci. Comput. 2017. V. 39. P. 88–111.
  5. Brandt A. Algebraic Mitigrid Teory: The Symmetric Case // J. Appl. Math. Comput. 1986. № 19. P. 23–56.
  6. Olshanskii M.A. Lecture Notes on Multigrid Methods. Inst. Vychisl. Mat., Ross. Akad. Nauk, Moscow, 2012.
  7. Saad Y. Iterative Mthods for Sparse Linear Systems, 2nd ed. SIAM, 2003.
  8. Olshanskii M.A., Tyryshnikov E.E. Iterative Methods for Linear Systems Theory and Applications, SIAM Philadelphia, 2014.
  9. Laevsky Y.M., Matsokin A.M. Decomposition Methods for Solving Elliptic and Parabolic Boundary Value Problems (in Russian). 1999. V. 2. P. 361–372.
  10. Korneev V.G. Fast Domain Decomposition Algorithms for Elliptic Problems with Piecewise Variable Orthotropies. in Apel T., Steinbach O. (eds) Advanced Finite Element Methods and Applications. Lecture Notes in Applied and Computational Mechanics, Springer, Berlin, Heidelberg, 2013. V. 66. doi: 10.1007/978-3-642-30316-6_3.
  11. Ильин В.П. Итерационные предобусловленные методы в крылова: тенденции XXI в. // Ж. вычисл. матем. и матем. физ. 2021. Т. 61. № 11. С. 1786–1813.
  12. Reusken A. A Multigrid Method Based on Incomplete Gaussian Elimination // Numer. Linear. Alg. Appl. 1996. V. 3. P. 369–390.
  13. Hackbusch W., Khoromskij B.N., Kriemann R. Direct Schur Complement Method by Domain Decomposition Based on H-Matrix Approximation // Comput. Visual. Sci. 2005. V. 8. № 3. P. 179–188. doi: 10.1007/s00791-005-0008-3
  14. Bornemann F.A., Deuflhard P. The Cascadic Multigrid Method for Elliptic Problems // Numerische Mathematik. 1996. Dec. V. 75. № 2. Р. 135–152. doi: 10.1007/s002110050234
  15. Shaidurov V.V. Some EVisitmates of the Rate of Convergence for the Cascadic Conjugate-Gradient Method // Comput. Math. Appl. 1996. V. 31. № 4. Р. 161–171. doi: 10.1016/0898-1221(95)00228-6. Selected Topics in Numerical Methods.
  16. Notay Y., Napov A. A Massively Parallel Solver for Discrete Poisson-like Problems // J. Comput. Phys. 2015. V. 281. Р. 237–250. doi: 10.1016/j.jcp.2014.10.043
  17. Ruge J.W., Stuben K. Algebraic Multigrid Multigrid Methods, 1987. Р. 73–130. doi: 10.1137/1.9781611971057.ch4
  18. Xu J., Zikatanov L. Algebraic Multigrid Methods // Acta Numerica. 2017. V. 26. Р. 591–721. doi: 10.1017/S0962492917000083
  19. Il'in V.P., Gurieva Y.L., Kozlov D.I. Parallel Domain Decomposition Methods with Graph Preconditioning. ПАВТ-23, Челябинск: Изд. ЮРГУ, 2023. С. 215–228.
  20. Il'in V.P. Multigrid Incomplete Factorization Methods in Krylov Subspaces // J. Math. Sci. Springer. 2023. V. 272. Р. 523–532.
  21. Batalov M., Il'in V. Multigrid Incomplete Factorization Methods in Krylov Subspaces on Unstructured Grids, Parallel Computational Technologies / ed. by L. Sokolinsky [et al.]. Cham : Springer Nature Switzerland, 2024. Р. 163–176.
  22. Кузнецов Ю.А. Алгебраические многосеточные методы декомпозиции области. М., Препринт № 232 ОВМ АН СССР, 1989. С. 05–516. Springer. Cham. doi: 10.1007/978-3-030-36592-9_41
  23. Bank R., Falgout R., Jones T., Manieuffel T., McCormick S., Ruge J. Algebraic Multigrid Domain and Range Decomposition (AMG-DD)/AMG-RDJ // SIAM J. Sci. Comput. 2015. V. 37. Р. 113–136.
  24. Ильин В.П. Методы и технологии конечных элементов. Новосибирск: Изд-во ИВМиМГ СО РАН, 2007. 370 с.
  25. Киглингвин L.A. Error Bounds for the Arnoldi Method: A Set of Extreme Eigenpairs // J. Numer. Linear Algebra Appl. 1999. V. 296. Р. 191–211.
  26. Il'in V.P. Biconjugate Direction Methods in Krylov Subspaces // J. Appl. Indust. Math. 2010. V. 4. № 1. Р. 65–78.
  27. Il'in V.P., D.I. Kozlov D.I., Petukhov A.V. On the Minimal Residual Methods for Solving Diffusion-Convection SLAEs // J. Phys.: Conf. Ser. 2021. V. 2099. Р. 012005.
  28. Notay Y. Flexible Conjugate Gradients // SIAM J. Sci. Comput. 2000. V. 22. Р. 1444–1460. doi: 10.1137/S1064827599362314
  29. Il'in V. Parallel Intelligent Computing in Algebraic Problems. Sokolinsky L., Zymbler M. (eds). Parallel Computational Technologies. РСТ 2021. Communications in Computer, 2021. Р. 108–117.
  30. Ильин В.П. Программирование ближайшего будущего: Концепция И Прагматика // Вестник РАН. 2023. Т. 93. № 2. С. 150–161. doi: 10.31857/S086958732302007X

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».