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

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

Авторы

  • И.Е. Капорин
  • О.Ю. Милюкова

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

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2020-01-11

Выпуск

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

Раздел

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

Авторы

И.Е. Капорин

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

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

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

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

  1. I. E. Kaporin, “A Preconditioned Conjugate-Gradient Method for Solving Discrete Analogs of Differential Problems,” Differ. Uravn. 26 (7), 1225-1236 (1990) [Differ. Equ. 26 (12), 897-906 (1990)].
  2. I. E. Kaporin, “New Convergence Results and Preconditioning Strategies for the Conjugate Gradient Method,” Numer. Linear Algebra Appl. 1 (2), 179-210 (1994).
  3. I. E. Kaporin and O. Yu. Milyukova, Incomplete Inverse Triangular Factorization in Parallel Algorithms of Preconditioned Conjugate Gradient Methods , Preprint No. 037 (Keldysh Institute of Applied Mathematics, Moscow, 2017).
  4. I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Explicitly Preconditioned Conjugate Gradient Method , Preprint No. 008 (Keldysh Institute of Applied Mathematics, Moscow, 2018).
  5. I. E. Kaporin and O. Yu. Milyukova, “MPI+OpenMP Parallel Implementation of the Conjugate Gradient Method with Factorized Explicit Preconditioners,” Voprosy Atomn. Nauki Tekhniki, Ser.: Mat. Mod. Fiz. Proc., No. 4, 57-69 (2018).
  6. T. A. Davis and Y. Hu, “The University of Florida Sparse Matrix Collection,” ACM Trans. Math. Softw. 38 (2011).
    doi 10.1145/2049662.2049663
  7. I. E. Kaporin and O. Yu. Milyukova, “Massively Parallel Preconditioned Conjugate Gradient Algorithm for the Numerical Solution of Linear Algebraic Equations,” in Optimization and Applications (Comput. Center Ross. Akad. Nauk, Moscow, 2011), Issue 2, pp. 132-157.
  8. P. A. Knight, “The Sinkhorn-Knopp Algorithm: Convergence and Applications,” SIAM J. Matrix Anal. Appl. 30 (1), 261-275 (2008).
  9. I. E. Kaporin, “Iterative Solution of Linear Systems Using the Incomplete Inverse Triangular Decomposition,” in Direct and Inverse Problems of Mathematical Physics (Mosk. Gos. Univ., Moscow, 1991), pp. 71-77.
  10. D. S. Kershaw, “The Incomplete Cholesky-Conjugate Gradient Method for the Iterative Solution of Systems of Linear Equations,” J. Comput. Phys. 26 (1), 43-65 (1978).
  11. H. Anzt, T. K. Huckle, J. Br854ckle, and J. Dongarra, “Incomplete Sparse Approximate Inverses for Parallel Preconditioning,” Parallel Comput. 71, 1-22 (2018).
  12. H. A. van der Vorst, “Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comput. 13 (2), 631-644 (1992).
  13. T. F. Chan and T. Szeto, “Composite Step Product Methods for Solving Nonsymmetric Linear Systems,” SIAM J. Sci. Comput. 17 (6), 1491-1508 (1996).
  14. Y. Saad and M. H. Schultz, “GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comput. 7 (3), 856-869 (1986).
  15. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, 1981).
  16. I. E. Kaporin, “Localization of the Eigenvalues of a Pencil of Positive Definite Matrices,” Zh. Vychisl. Mat. Mat. Fiz. 48 (11), 1923-1931 (2008) [Comput. Math. Math. Phys. 48 (11), 1917-1926 (2008)].
  17. I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Implementation of BiCGStab Method with Factorized Explicit Preconditioner , Preprint No. 047 (Keldysh Institute of Applied Mathematics, Moscow, 2019).