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

MPI+OpenMP implementation of conjugate gradients method with preconditioner of the block incomplete inverse triangular decomposition of the first order

Authors

  • Olga Yu. Milyukova

Keywords:

implicit block preconditioning
incomplete Cholesky factorization
parallel preconditioning
conjugate gradient method

Abstract

The paper considers the preconditioner of the block incomplete inverse triangular decomposition of the first order “by value” BIIC-IC1 for solving systems of linear algebraic equations with a symmetric positively defined matrix. A method of using MPI+OpenMP technology for constructing and inverting the BIIC-IC1 preconditioner, in which the number of blocks in the preconditioner is a multiple of the number of used processors and used threads, is considered. A method is proposed for using the MPI+OpenMP technology to construct and invert the BIICIC1 preconditioner, in which a special ordering of grid nodes within subdomains corresponding to processor calculations is used to apply the OpenMP technology. The time of solving problems by the conjugate gradient method with the BIIC-IC1 preconditioner using MPI and hybrid MPI + OpenMP technology is compared on the example of a model problem and a number of problems from the collection of sparse matrices SuiteSparse.

Downloads

Published

2022-08-23

Issue

Vol. 23 (2022): Issue 3.

Section

Parallel software tools and technologies

Author Biography

Olga Yu. Milyukova

Keldysh Institute of Applied Mathematics of RAS
• Leading Researcher

References

  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.

License

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.