Some ways of parallel implementation of the conjugate gradient method with an implicit factorized preconditioner

O. Yu. Milyukova

Matematičeskoe modelirovanie, Tome 36 (2024) no. 2, pp. 174-196.

Résumé

The paper considers two ways of using MPI and MPI+OpenMP technologies for constructing and inverting the preconditioner of an incomplete triangular Cholesky decomposition without filling IC(0) for solving systems of linear algebraic equations with an arbitrary symmetric positive definite matrix. They differ in the way in which the preconditioning matrix IC(0) is computed. Methods of using MPI and MPI+OpenMP technologies are based on the use of grid node orderings consistent with the division of the calculation area. Comparative timing results for the MPI+OpenMP and MPI implementations of the proposed preconditioning used with the conjugate gradient method for a model problems and the sparse matrix collections SuiteSpars e as well as comparing the time of solving these problems using two methods of using MPI and MPI + OpenMP technology are presented.

Détail

Keywords: incomplete Cholesky factorization, Domain Decomposition ordering, parallel preconditioning, conjugate gradient method.

Bibliographie

[1] J. A. Meijering, H. A. van der Vorst, “An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix”, Math. Comp., 31 (1977), 148–162 | MR

[2] J. Ortega, Introduction to parallel and vector solution of linear systems, NY., 1988 | MR | Zbl

[3] I. S. Duff, G. A. Meurant, “The effect of ordering on preconditioned conjugate gradients”, BIT, 29 (1989), 625–657 | DOI | MR

[4] S. Doi, “On parallelism and convergence of incomplete LU factorizations”, Applied Numerical Mathematics: Transactions of IMACS, 7:5 (1991), 417–436 | DOI | MR | Zbl

[5] Y. Notay, “An efficient parallel discrete PDE solver”, Parallel Computing, 21 (1995), 1725–1748 | DOI | MR

[6] O. Yu. Milyukova, “Parallel approximate factorization method for solving discreate elliptic equations”, Parallel Computing, 27:10 (2001), 1365–1379 | DOI | MR | Zbl

[7] O. Yu. Milyukova, “Parallel Iterative Methods Using Factorized Preconditioning Matrices for Solving Elliptic Equations on Triangular Grids”, J. Comput. Math. Math. Phys., 46:6 (2006), 1044–1060 | DOI | MR

[8] D. Hysom, A. Pothen, “A scalable parallel algorithm for incomplete factor preconditioning”, SIAM J. Sci. Comput., 22:6 (2001), 2194–2215 | DOI | MR | Zbl

[9] M. Magolu Monga Made, H. A. van der Vorst, “Spectral analysis of parallel incomplete factorizations with implicit pseudo-overlap”, Num. Linear Algebra Appl, 9:1 (2002), 45–64 | DOI | MR | Zbl

[10] O. Yu. Milyukova, “Combination of Numerical and Structured Approaches to the Construction of a Second-Order Incomplete Triangular Factorization in Parallel Preconditioning Methods”, J. Comput. Math. Math. Phys., 56:5, 699–716 | DOI | DOI | MR | Zbl

[11] I. E. Kaporin, “High quality preconditionings of a general symmetric positive definite matrix based on its decomposition”, Numer. Lin. Alg. Appl., 5:6 (1998), 483–509 | 3.0.CO;2-7 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[12] I. E. Kaporin, I. N. Kon'shin, “Parallel solution of symmetric positive definite systems based on decomposition into overlapping blocks”, Comput. Math. Math. Phys., 41:4 (2001), 481–493 | MR | Zbl

[13] I. E. Kaporin, O. Yu. Miliukova, Massivno-parallelnyi algoritm predobuslovlennogo metoda sopriazhennykh gradientov dlia chiclennogo resheniia system lineinykh algebraicheskikh uravnenii, Izd-vo VTs RAN, M., 2011, 132–157

[14] O. Yu. Milyukova, “MPI+OpenMP parallel implementation of conjugated gradient method with the IC(0) preconditioners of block incomplete inverse triangular decomposition of second and first order”, Proc. VANT, Ser.: Mat. Mod. Fiz., 2022, no. 1, 48–61 | DOI

[15] I. E. Kaporin, “New convergence results and preconditioning strategies for conjugate gradient method”, Numer. Linear Algebra and Appl., 1:2 (1994), 179–210 | DOI | MR | Zbl

[16] N. Munksgaard, “Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients”, ACM Trans. Math. Software, 1980, no. 6, 206–219 | DOI | Zbl

[17] O. Yu. Milyukova, “MPI+OpenMPI realizatsiia metoda sopriazhennykh gradientov s faktorizovannym predobuslovlivatelem”, Keldysh Institute preprints, 2020, 031, 22 pp.

[18] O. Yu. Milyukova, “MPI+OpenMP Implementation of the Conjugated Gradient Method with Factorized Implicit Preconditioners”, MM, 14:3 (2022), 367–380 | MR

[19] O. Yu. Milyukova, “MPI+OpenMP realizatsiia metoda sopriazhennykh gradientov s predobuslovliteliami blochnogo nepolnogo obratnogo treugolnogo razlozheniia pervogo poriadka”, Vychislitel'nye Metody i Programmirovanie, 23:3 (2022), 191–206 | MR

[20] O. Yu. Milyukova, “Sposoby MPI+OpenMP realizatsii metoda sopriazhennykh gradientov s predobuslovlivatelem IC(0) na osnove ispolzovaniia pereuporiadocheniia uzlov setki”, Keldysh Institute preprints, 2023, 035, 32 pp.

[21] O. Yu. Milyukova, “MPI+OpenMP realizatsiia metoda sopriazhennykh gradientov s faktorizovannym predobuslovlivatelem na osnove ispolzovaniia pereuporiadocheniia uzlov setki”, Keldysh Institute preprints, 2023, 018, 29 pp.

[22] D. Kershow, “The Incomplete Choleski-conjugate gradient method for the iterative solution of systems of linear equations”, J. Comp. Phys., 26 (1978), 43–65 | DOI | MR

[23] I. E. Kaporin, O. Yu. Milyukova, “Nepolnoe obratnoe treugolnoe razlozhenie v parallelnykh algoritmakh predobuslovlennogo metoda sopriazhennykh gradientov”, Keldysh Institute preprints, 2017, 037, 28 pp.

[24] T. Davis, Y. F. Hu, “University of Florida sparse matrix collection”, ACM Trans. on Math. Software, 38:1 (2011) | MR

[25] O. Axelsson, Iterative solution methods, Cambridge Univ. Press, New York, 1994 | MR | Zbl

[26] I.E. Kaporin, “Using Chebyshev polynomials and approximate inverse triangular decomposition to pre-condition the conjugate gradient method”, J. Comp. Math. Math. Phys., 52:2 (2012), 169–193 | DOI | MR | Zbl