MPI+OpenMP parallel implementation of conjugate gradient method with factored implicit preconditioners

O. Yu. Milyukova

Matematičeskoe modelirovanie, Tome 33 (2021) no. 10, pp. 19-38.

Résumé

Non-iterative algorithms based on MPI+OpenMP techniques are proposed for the construction and application of the Block Jacobi preconditioner combined with incomplete parameter-trimmed decomposition IC1 and stabilized incomplete parameter-trimmed decomposition IC2S. At the same time, the number of blocks in the Jacobi block is a multiple of the number of processors used and the number of threads used. Estimates of the number of iterations of conjugate gradients method with the Block Jacobi preconditioner combined with IC1 or IC2S methods obtained. Using model tasks calculations and a number of tasks from the sparse matrix collection SuiteSparse shown that the use of MPI+OpenMP technology makes it possible to significantly speed up calculations compared to the use of only MPI for not too many nodes of a supercomputer system.

Détail

Mots-clés : sparse matrixes
Keywords: conjugate gradient method, incomplete Cholesky factorization, parallel computing.

Bibliographie

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

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

[3] A. D. Tuff, A. Jennings, “An iterative method for large systems of linear structural equations”, J. Num. Methods Eng., 1973, no. 7, 175–183 | DOI | MR | Zbl

[4] E. C. Anderson, Y. Saad, “Solving sparse triangular systems on parallel computers”, International J. of High Speed Computing, 1 (1989), 73–96 | DOI

[5] S. W. Hammond, R. Schreiber, “Efficient ICCG on a shared memory multiprocessor”, International J. High Speed Computing, 4 (1992), 1–21 | DOI

[6] M. M. Wolf, M. A. Heroux, E. G. Boman, “Factors impacting performance of 535 multithreaded sparse triangular solve”, Proc. of the 9th Inter. Conf. on High Performance Computing for Computational Sci., VECPAR'10, Springer-Verlag, Berlin–Heidelberg, 2011, 32–44 | Zbl

[7] E. Chow, H. Anzt, J. Scott, J. Dongarra, “Using Jacobi iterations and blocking for solving sparse triangular systems in incomplete factorization preconditioning”, Journal of Parallel and Distributed Computing, 2018, no. 119, 219–230 | DOI

[8] E. Chow, A. Patel, “Fine-grained parallel incomplete LU factorization”, SIAM J. Sci. Comput, 37 (2015), 169–193 | MR

[9] S. Cayrols, I. Duff, 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, Science Technology Facilities Council, UK, 2018, 27 pp. | Zbl

[10] I.E Kaporin, O. Iu. Miliukova, “MPI+OpenMP parallelnaya realizatsiia metoda sopriazhennykh gradientov s nekotorymi iavnymi predobuslovlivateliami”, Preprinty IPM im. M.V. Keldysha RAN, 2018, 008, 28 pp.

[11] I.E Kaporin, O. Iu. MiLiukova, “MPI+OpenMP realizatsiia metoda sopriazhennykh gradientov s faktorizovannymi iavnymi predobuslovlivateliami”, VANT Seriia Matematicheskoe modelirovanie fizicheskikh protsessov, 2018, no. 4, 57–69

[12] E. Chow, “Parallel implementation and practical use of sparse approximate inverse preconditioners with a priori sparsity patterns”, Inter. J. High Performance Comput. Appl., 15:1 (2001), 56–74 | DOI | MR

[13] O. Iu. MiLiukova, “MPI+OpenMP realizatsiia metoda sopriazhennykh gradientov s faktorizovannym predobuslovlivateliam”, Preprinty IPM im. M.V. Keldysha RAN, 2020, 031, 22 pp.

[14] O. Iu. MiLiukova, “MPI+OpenMP realizatsiia metoda sopriazhennykh gradientov s predobuslovlivateliam blochnogo Yakobi IC1”, Preprinty IPM im. M.V. Keldysha RAN, 2020, 083, 28 pp.

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

[16] I. E. Kaporin, O. Iu. MiLiukova, “Nenolnoe obratnoe treugolnoe razlozhenie v parallelnyh algoritmah predobuslovlennogo metoda sopriazhennykh gradientov”, Preprinty IPM im. M.V. Keldysha RAN, 2017, 037, 28 pp.

[17] T. Davis, Y. F. Hu, “University of Florida sparse matrix collection”, ACM Trans. on Math. Software, 38:1 (2011) http://www.cise.ufl.edu/research/sparse/matrices | MR

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

[19] M. Tismenetsky, “A new preconditioning technique for solving large sparse linear systems”, Linear Algebra Appls., 154–156 (1991), 331–353 | DOI | MR | Zbl

[20] M. Suarjana, K. H. Law, “A robust incomplete factorization based on value and space constraints”, Int. J. Numer. Methods Engrg., 38 (1995), 1703–1719 | DOI | MR | Zbl

[21] T. A. Manteuffel, “An incomplete factorization technique for positive definite linear systems”, Math. Comput., 34 (1980), 473–497 | DOI | MR | Zbl

[22] I. Yamazaki, Z. Bai, W. Chen, R. Scalettar, “A High-Quality Preconditioning Technique for Multi-Length-Scale Symmetric Positive Definite Linear Systems”, Numer. Math. Theor. Meth. Appl., 2:2 (2009), 469–484 | DOI | MR | Zbl

[23] A. Jennigs, G. M. Malik, “Partial elimination”, J. Inst. Math. Appl., 20 (1977), 307–316 | DOI | MR

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