MPI+OpenMP реализация метода BiCGStab с явным предобусловливанием для решения разреженных систем линейных алгебраических уравнений

Авторы

  • И.Е. Капорин Вычислительный центр имени А.А. Дородницына РАН (ВЦ РАН)
  • О.Ю. Милюкова Институт прикладной математики имени М.В. Келдыша РАН (ИПМ РАН)

DOI:

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

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

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

Аннотация

Для предобусловливания несимметричной положительно определенной разреженной матрицы рассматривается ее приближенная обратная, представленная в виде произведения нижнетреугольной и верхнетреугольной матриц. Предлагается новый способ предобусловливания положительно определенной разреженной матрицы- метод блочного Якоби неполного обратного LU-разложения. Описан алгоритм параллельной реализации метода BiCGStab с предложенным предобусловливанием с применением MPI+OpenMP-технологии. Проводится сравнение времени решения тестовых задач из коллекции разреженных матриц SuiteSparse (ранее известной как коллекция университета Флориды) методом BiCGStab с предложенным предобусловливанием и с предобусловливанием Якоби, а также с предобусловливанием блочного Якоби в сочетании с неполным треугольным разложением без заполнения. При этом используются разработанные параллельные реализации на основе MPI- или MPI+OpenMP-подходов.

Авторы

И.Е. Капорин

Вычислительный центр имени А.А. Дородницына РАН (ВЦ РАН)
ул. Вавилова, 40, 119333, Москва
• главный научный сотрудник

О.Ю. Милюкова

Институт прикладной математики имени М.В. Келдыша РАН (ИПМ РАН)
Миусская пл., 4, 125047, Москва
• ведущий научный сотрудник

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

  1. Капорин И.Е. О предобусловливании метода сопряженных градиентов при решении дискретных аналогов дифференциальных задач // Дифференциальные уравнения. 1990. 26, № 7. 1225-1236.
  2. Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra Appl. 1994. Vol. 1, N 2. 179-210.
  3. Капорин И.Е., Милюкова О.Ю. Неполное обратное треугольное разложение в параллельных алгоритмах предобусловленного метода сопряженных градиентов. Препринт № 037 ИПМ им. М.В. Келдыша. М., 2017.
  4. Капорин И.Е., Милюкова О.Ю. MPI+OpenMP параллельная реализация метода сопряженных градиентов с некоторыми явными предобусловливателями. Препринт № 008 ИПМ им. М.В. Келдыша. М., 2018.
  5. Капорин И.Е., Милюкова О.Ю. MPI+OpenMP реализация метода сопряженных градиентов с факторизованными явными предобусловливателями // Вопросы атомной науки и техники. Серия математическое моделирование физических процессов. 2018. Вып. 4. 57-69.
  6. Davis T.A., Hu Y. The university of Florida sparse matrix collection // ACM Trans. on Math. Software. 2011. Vol. 38, N 1. doi 10.1145/2049662.2049663.
  7. Капорин И.Е., Милюкова О.Ю. Массивно-параллельный алгоритм предобусловленного метода сопряженных градиентов для численного решения систем линейных алгебраических уравнений // Сб. Трудов отдела проблем прикладной оптимизации ВЦ РАН. М.: Изд-во ВЦ РАН, 2011. 132-157.
  8. Knight P.A. The Sinkhorn-Knopp algorithm: convergence and applications // SIAM J. Matrix Anal. Appl. 2008. Vol. 30, N 1. 261-275.
  9. Капорин И.Е. Итерационное решение систем линейных уравнений с использованием неполной обратной треугольной факторизации // Прямые и обратные задачи математической физики. М.: Изд-во МГУ, 1991. 71-77.
  10. Kershaw D.S. The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations // Journal of Computational Physics. 1978. Vol. 26, N 1. 43-65.
  11. Anzt H., Huckle T.K., Brackle J., Dongarra J. Incomplete sparse approximate inverses for parallel preconditioning // Parallel Computing. 2018. Vol. 71. 1-22.
  12. Van der Vorst H.A. Bi-CGStab: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems // SIAM J. Sci. Stat. Comput. 1992. Vol. 13, N 2. 631-644.
  13. Chan T.F., Szeto T. Composite step product methods for solving nonsymmetric linear systems // SIAM Journal on Scientific Computing. 1996. Vol. 17, N 6. 1491-1508.
  14. Saad Y., Schultz M.H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM Journal on Scientific and Statistical Computing. 1986. Vol. 7, N 3. 856-869.
  15. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984.
  16. Капорин И.Е. Локализация собственных значений пучка положительно-определенных матриц // Ж. вычисл. матем. и матем. физ. 2008. 48, № 11. 1923-1931.
  17. Капорин И.Е., Милюкова О.Ю. MPI+OpenMPI реализация метода BiCGStab c факторизованным явным предобусловливателем. Препринт № 047 ИПМ им. М.В. Келдыша. М., 2019.
Новые вычислительные технологии

Загрузки

Опубликован

2020-01-11

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

Капорин И.Е., Милюкова О.Ю. MPI+OpenMP реализация метода BiCGStab с явным предобусловливанием для решения разреженных систем линейных алгебраических уравнений // Вычислительные методы и программирование. 2020. 20. 516-527. doi 10.26089/NumMet.v20r445

Выпуск

Том 20 (2019): Выпуск 4.

Раздел

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