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

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

Авторы

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

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

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

Аннотация

В работе рассматривается предобусловливатель блочного неполного обратного треугольного разложения первого порядка “по значению” BIIC-IC1 для решения систем линейных алгебраических уравнений с симметричной положительно определенной матрицей. Рассматривается способ применения MPI+OpenMP технологии для построения и обращения предобусловливателя BIIC-IC1, при этом в предобусловливателе число блоков кратно числам используемых процессоров и используемых потоков. Предлагается способ применения MPI+OpenMP технологии для построения и обращения предобусловливателя BIIC-IC1, в котором для применения OpenMP технологии используется специальное упорядочение узлов сетки внутри подобластей, соответствующих расчетам на процессорах. Проводится сравнение времени решения задач методом сопряженных градиентов с предобусловливателем BIIC-IC1 с использованием MPI и гибридной MPI+OpenMP технологии на примере модельной задачи и ряда задач из коллекции разреженных матриц SuiteSparse.

Загрузки

Опубликован

2022-08-23

Выпуск

Том 23 (2022): Выпуск 3.

Раздел

Параллельные программные средства и технологии

Автор

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

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

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

  1. I. E. Kaporin, “New Convergence Results and Preconditioning Strategies for the Conjugate Gradient Method,” Numer. Linear Algebra Appl. 1 (2), 179-210 (1994).
  2. 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 (7), 897-906 (1990)].
  3. O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Preconditioner of Block Partial Inverse Triangular Decomposition of IC2S and IC1 , Preprint No. 48 (Keldysh Institute of Applied Mathematics, Moscow, 2021).
    doi 10.20948/prepr-2021-48.
  4. N. Munksgaard, “Solving Sparse Symmetric Sets of Linear Equations by Preconditioned Conjugate Gradients,” ACM Trans. Math. Softw. 6 (2), 206-219 (1980).
  5. A. D. Tuff and A. Jennings, “An Iterative Method for Large Systems of Linear Structural Equations,” Int. J. Numer. Methods Eng. 7 (2), 175-183 (1973).
  6. M. A. Ajiz and A. Jennings, “A Robust Incomplete Choleski-Conjugate Gradient Algorithm,” Int. J. Numer. Methods Eng. 20 (5), 949-966 (1984).
  7. I. E. Kaporin, “High Quality Preconditionings of a General Symmetric Positive Definite Matrix Based on Its U^TU+U^TR+R^TU-Decomposition,” Numer. Linear Algebra Appl. 5 (6), 483-509 (1998).
  8. I. E. Kaporin, Preconditioning of Systems of Linear AlgebraicEquations. Doctoral Dissertation in Mathematics and Physics (Moscow State Univ., Moscow, 2011).
  9. I. E. Kaporin and I. N. Kon’shin, “Parallel Solution of Symmetric Positive Definite Systems Based on Decomposition into Overlapping Blocks,” Zh. Vychisl. Mat. Mat. Fiz. 41 (4), 515-528 (2001) [Comput. Math. Math. Phys. 41 (4), 481-493 (2001)].
  10. 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. 32-49.
  11. I. S. Duff and G. A. Meurant, “The Effect of Ordering on Preconditioned Conjugate Gradients,” BIT Numer. Math. 29, 635-657 (1989).
  12. S. Doi, “On Parallelism and Convergence of Incomplete LU Factorizations,” Appl. Numer. Math. 7 (5), 417-436 (1991).
    doi 10.1016/0168-9274(91)90011-N.
  13. Y. Notay, “An Efficient Parallel Discrete PDE Solver,” Parallel Comput. 21 (11), 1725-1748 (1995).
    doi 10.1016/0167-8191(96)80005-6.
  14. O. Yu. Milyukova, “Parallel Approximate Factorization Method for Solving Discrete Elliptic Equations,” Parallel Comput. 27 (10), 1365-1379 (2001).
    doi 10.1016/S0167-8191(01)00092-8.
  15. O. Yu. Milyukova, “Parallel Iterative Methods Using Factorized Preconditioning Matrices for Solving Elliptic Equations on Triangular Grids,” Zh. Vychisl. Mat. Mat. Fiz. 46 (6), 1096-1113 (2006) [Comput. Math. Math. Phys. 46 (6), 1044-1060 (2006)].
    doi 10.1134/S096554250606011X.
  16. D. Hysom and A. Pothen, “A Scalable Parallel Algorithm for Incomplete Factor Preconditioning,” SIAM J. Sci. Comput. 22 (6), 2194-2215 (2001).
    doi 10.1137/S1064827500376193.
  17. M. Magolu monga Made and H. A. van der Vorst, “Spectral Analysis of Parallel Incomplete Factorizations with Implicit Pseudo-Overlap,” Numer. Linear Algebra Appl. 9 (1), 45-64 (2002).
    doi 10.1002/nla.247.
  18. O. Yu. Milyukova, “Combination of Numerical and Structured Approaches to the Construction of a Second-Order Incomplete Triangular Factorization in Parallel Preconditioning Methods,” Zh. Vychisl. Mat. Mat. Fiz. 56 (5), 711-729 (2016) [Comput. Math. Math. Phys. 56 (5), 699-716 (2016)].
    doi 10.1134/S096554251605016X.
  19. E. C. Anderson and Y. Saad, “Solving Sparse Triangular Systems on Parallel Computers,” Int. J. High Speed Comput. 1, 73-96 (1989).
  20. S. W. Hammond and R. Schreiber, “Efficient ICCG on a Shared Memory Multiprocessor,” Int. J. High Speed Comput. 4 (01), 1-21 (1992).
    doi 10.1142/S0129053392000183.
  21. M. M. Wolf, M. A. Heroux, and E. G. Boman, “Factors Impacting Performance of Multithreaded Sparse Triangular Solve,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2011), Vol. 6449, pp. 32-44.
    doi 10.1007/978-3-642-19328-6_6.
  22. E. Chow, H. Anzt, J. Scott, and J. Dongarra, “Using Jacobi Iterations and Blocking for Solving Sparse Triangular Systems in Incomplete Factorization Preconditioning,” J. Parallel Distrib. Comput. 119, 219-230 (2018).
    doi 10.1016/j.jpdc.2018.04.017.
  23. E. Chow and A. Patel, “Fine-Grained Parallel Incomplete LU Factorization,” SIAM J. Sci. Comput. 37 (2), 169-193 (2015).
    doi 10.1137/140968896.
  24. S. Cayrols, I. Duff, and F. Lopes, Parallelization of the Solve Phase in a Task-based Cholesky Solver Using a Sequential Task Flow Model , Technical Report RAL-TR-2018-008 (Harwell, Oxford, 2018).
  25. I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Explicitly Preconditioned Conjugate Gradient Method , Preprint No. 8 (Keldysh Institute of Applied Mathematics, Moscow, 2018).
    doi 10.20948/prepr-2018-8.
  26. 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. Issue 4, 57-69 (2018).
  27. E. Chow, “Parallel Implementation and Practical Use of Sparse Approximate Inverse Preconditioners with a Priori Sparsity Patterns,” Int. J. High Perform. Comput. Appl. 15 (1), 56-74 (2001).
    doi 10.1177/109434200101500106.
  28. O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Factorized Preconditioner , Preprint No. 31 (Keldysh Institute of Applied Mathematics, Moscow, 2020).
    doi 10.20948/prepr-2020-31.
  29. O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with the Block Jacobi Preconditioner Combined with IC1 , Preprint No. 83 (Keldysh Institute of Applied Mathematics, Moscow, 2020).
    doi 10.20948/prepr-2020-83.
  30. O. Yu. Milyukova, “MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Factored Implicit Preconditioners,” Mat. Model. 33 (10), 19-38 (2021)
    doi 10.20948/mm-2021-10-02.
  31. O. Yu. Milyukova, Approaches MPI+OpenMP Implementation of Conjugated Gradient Method with Pre-conditioner of Block Incomplete Inverse Triangular Decomposition of IC1 , Preprint No. 2 (Keldysh Institute of Applied Mathematics, Moscow, 2022).
    doi 10.20948/prepr-2022-2.
  32. I. E. Kaporin and O. Yu. Milyukova, Incomplete Inverse Triangular Factorization in Parallel Algorithms of Preconditioned Conjugate Gradient Methods , Preprint No. 37 (Keldysh Institute of Applied Mathematics, Moscow, 2017).
    doi 10.20948/prepr-2017-37.
  33. T. A. Davis and Y. Hu, “The University of Florida Sparse Matrix Collection,” ACM Trans. Math. Softw. 38 (1), 1: 1-1: 25 (2011).
    doi 10.1145/2049662.2049663.
  34. O. Axelsson, Iterative Solution Methods (Cambridge Univ. Press, New York, 1994).
  35. I. E. Kaporin, “Using Chebyshev Polynomials and Approximate Inverse Triangular Factorizations for Preconditioning the Conjugate Gradient Method,” Zh. Vychisl. Mat. Mat. Fiz. 52 (2), 179-204 (2012) [Comput. Math. Math. Phys. 52 (2), 169-193 (2012)].
    doi 10.1134/S0965542512020091.

Лицензия

Copyright (c) 2022 О. Ю. Милюкова

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.