Алгебро-геометрические и информационные структуры методов декомпозиции областей

Авторы

  • Я.Л. Гурьева Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
  • В.П. Ильин Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
  • Д.В. Перевозкин Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)

DOI:

https://doi.org/10.26089/NumMet.v17r213

Ключевые слова:

декомпозиция областей, большие системы линейных уравнений, разреженные матрицы, структуры данных, гибридное программирование, параллельное программирование

Аннотация

Рассматриваются алгебраические, геометрические и информационные аспекты параллельных методов декомпозиции для решения больших систем линейных уравнений с разреженными матрицами, возникающими при аппроксимации многомерных краевых задач на неструктурированных сетках. Алгоритмы базируются на разбиении сеточной расчетной области на подобласти с параметризованной величиной пересечений и различными интерфейсными условиями на смежных границах. Рассматриваются вопросы, возникающие при алгебраической декомпозиции исходной матрицы. Применяются различные двухуровневые итерационные процессы, включающие в себя предобусловленные крыловские методы с использованием грубосеточной коррекции, а также синхронное решение вспомогательных систем в подобластях с помощью прямых или итерационных алгоритмов. Распараллеливание алгоритмов реализуется средствами гибридного программирования с формированием MPI-процессов для каждой подобласти и использованием в них многопотоковых вычислений над общей памятью. Информационные коммуникации между соседними подобластями осуществляются на каждой внешней итерации путем предварительной организации буферов обмена и применения неблокирующих операций с возможностями проведения арифметических действий на фоне передачи данных.

Авторы

Я.Л. Гурьева

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
просп. Лаврентьева, 6, 630090, Новосибирск
• старший научный сотрудник

В.П. Ильин

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
просп. Лаврентьева, 6, 630090, Новосибирск
• главный научный сотрудник

Д.В. Перевозкин

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
просп. Лаврентьева, 6, 630090, Новосибирск
• младший научный сотрудник

Библиографические ссылки

  1. R. Rabenseifner, G. Hager, and G. Jost, “Hybrid MPI and OpenMP Parallel Programming. MPI+OpenMP and Other Models on Clusters of SMP nodes,” Tutorial tut123 at SC13, November 17, 2013, Denver (CO) USA.
    http://openmp.org/sc13/HybridPP_Slides.pdf . Cited April 5, 2016.
  2. V. P. Il’in, “DELAUNAY: A Technological Environment for Grid Generation,” Sib. Zh. Ind. Mat. 16 (2), 83-97 (2013).
  3. Domain Decomposition Methods.
    http://www.ddm.org . Cited April 5, 2016.
  4. A. Toselli and O. B. Widlund, Domain Decomposition Methods: Algorithms and Theory (Springer, Heidelberg, 2005).
  5. Y. L. Gurieva and V. P. Il’in, “On Parallel Computational Technologies of Augmented Domain Decomposition Methods,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2015), Vol. 9251, pp. 35-46.
  6. V. Dolean, P. Jolivet, and F. Nataf, “An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation,”
    https://hal.archives-ouvertes.fr/cel-01100932v4/document . Cited April 5, 2016.
  7. V. P. Il’in, “Parallel Methods and Technologies of Domain Decomposition,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. No. 46, 31-44 (2012).
  8. I. A. Klimonov, V. D. Korneev, and V. M. Sveshnikov, “Parallelization Technologies for Solving Three-Dimensional Boundary Value Problems on Quasi-Structured Grids Using the CPU+GPU Hybrid Computing Environment,” Vychisl. Metody Programm. 17, 65-71 (2016).
  9. V. P. Il’in and D. V. Perevozkin, “On Some Variants of Domain Decomposition Methods,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. 3 (2), 5-19 (2014).
  10. ParMETIS - Parallel Graph Partitioning and Fill-Reducing Matrix Ordering.
    http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview . Cited April 5, 2016.
  11. G. Karypis, “METIS - Serial Graph Partitioning and Fill-Reducing Matrix Ordering,”
    http://glaros.dtc.umn.edu/gkhome/metis/metis/overview . Cited April 5, 2016.
  12. S. Pissanetzky, Sparse Matrix Technology (Academic, London, 1984; Mir, Moscow, 1988).
  13. D. S. Butyugin, Y. L. Guryeva, V. P. Il’in, et al., “Parallel Algebraic Solvers Library Krylov,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. 2 (3), 92-105 (2013).

Загрузки

Опубликован

2016-04-12

Как цитировать

Гурьева Я.Л., Ильин В.П., Перевозкин Д.В. Алгебро-геометрические и информационные структуры методов декомпозиции областей // Вычислительные методы и программирование. 2016. 17. 132-146. doi 10.26089/NumMet.v17r213

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Наиболее читаемые статьи этого автора (авторов)