Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method

I. E. Kaporin

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 2, pp. 179-204

Résumé

In order to precondition a sparse symmetric positive definite matrix, its approximate inverse is examined, which is represented as the product of two sparse mutually adjoint triangular matrices. In this way, the solution of the corresponding system of linear algebraic equations (SLAE) by applying the preconditioned conjugate gradient method (CGM) is reduced to performing only elementary vector operations and calculating sparse matrix-vector products. A method for constructing the above preconditioner is described and analyzed. The triangular factor has a fixed sparsity pattern and is optimal in the sense that the preconditioned matrix has a minimum K-condition number. The use of polynomial preconditioning based on Chebyshev polynomials makes it possible to considerably reduce the amount of scalar product operations (at the cost of an insignificant increase in the total number of arithmetic operations). The possibility of an efficient massively parallel implementation of the resulting method for solving SLAEs is discussed. For a sequential version of this method, the results obtained by solving 56 test problems from the Florida sparse matrix collection (which are large-scale and ill-conditioned) are presented. These results show that the method is highly reliable and has low computational costs.

Bibliographie

[1] Garanzha V.A., Golikov A.I., Evtushenko Yu.G., Nguen M.Kh., “Parallelnaya realizatsiya metoda Nyutona dlya resheniya bolshikh zadach lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 49:8 (2009), 1369–1384 | MR | Zbl

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

[3] George T., Gupta A., Sarin V., An experimental evaluation of iterative solvers for large SPD systems of linear equations, IBM Res. Report RC 24479, Jan. 25, 2008

[4] Kaporin I.E., “Predobuslovlennyi metod sopryazhennykh gradientov dlya resheniya diskretnykh analogov differentsialnykh zadach”, Differents. ur-niya, 26:7 (1990), 1225–1236 | MR | Zbl

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

[6] Kolotilina L.Yu., Yeremin A.Yu., “Factorized sparse approximate inverse preconditionings. I. Theory”, SIAM J. Matrix Anal. Appl., 14 (1993), 45–58 | DOI | MR | Zbl

[7] Chow E., “A priori sparsity patterns for parallel sparse approximate inverse preconditioners”, SIAM J. Sci. Comput., 21:5 (2000), 1804–1822 | DOI | MR | Zbl

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

[9] Kolotilina L.Yu., Nikishin A.A., Yeremin A.Yu., “Factorized sparse approximate inverse preconditionings. IV. Simple approaches to rising efficiency”, Numer. Linear Algebra Appl/, 6 (1999), 515–531 | 3.0.CO;2-0 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] Kaporin I.E., “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 (1998), 483–509 | 3.0.CO;2-7 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[11] Benzi M., Tuma T., “A robust incomplete factorization preconditioner for positive definite matrices”, Numer. Linear Algebra Appl., 10 (2003), 385–400 | DOI | MR | Zbl

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

[13] Kaporin I.E., “Explicitly preconditioned conjugate gradient method for the solution of nonsymmetric linear systems”, Internat. J. Comput. Math., 40 (1992), 169–187 | DOI

[14] Kaporin I.E., Konshin I.N., “Parallelnoe reshenie simmetrichnykh polozhitelno-opredelennykh sistem na osnove perekryvayuschegosya razbieniya na bloki”, Zh. vychisl. matem. i matem. fiz., 41:4 (2001), 515–528 | MR | Zbl

[15] Kaporin I.E., Konshin I.N., “Postfiltratsiya mnozhitelei IC2-razlozheniya dlya balansirovki parallelnogo predobuslovlivaniya”, Zh. vychisl. matem. i matem. fiz., 49:6 (2009), 940–957 | MR | Zbl

[16] Notay Y., “On the convergence rate of the conjugate gradients in presence of rounding errors”, Numer. Math., 65 (1993), 301–317 | DOI | MR | Zbl

[17] Jennings A., “Influence of the eigenvalue spectrum on the convergence rate of the conjugate gradient method”, J. Instit. Math. and Its Applic., 20 (1977), 61–72 | DOI | MR | Zbl

[18] Axelsson O., Lindskog G., “On the rate of convergence of the preconditioned conjugate gradient method”, Numer. Math., 48:5 (1986), 499–523 | DOI | MR | Zbl

[19] Lebedev V.I., Finogenov S.A., “O poryadke vybora iteratsionnykh parametrov v chebyshevskom tsiklicheskom iteratsionnom metode”, Zh. vychisl. matem. i matem. fiz., 11:2 (1971), 425–438 | MR | Zbl

[20] Field M. R., “Adaptive polynomial preconditioning for the conjugate gradient algorithm”, Appl. Parallel Comput. in Phys., Chemistry and Engineering Science, Lecture Notes in Computer Science, 1041, 1996, 189–198 | DOI

[21] Saad Y., “Practical use of polynomial preconditionings for the conjugate gradient method”, SIAM J. Sci. and Statist. Comput., 6:4 (1985), 865–881 | DOI | MR | Zbl

[22] Johnson O.G., Micchelli C.A., Paul G., “Polynomial preconditioning for conjugate gradient calculations”, SIAM J. Numer. Anal., 20 (1983), 362–376 | DOI | MR | Zbl

[23] Ashby S.F., Manteuffel T.A., Otto.J.S., “A comparison of adaptive Chebyshev and least squares polynomial preconditioning for hermitian positive definite linear systems”, SIAM J. Sci. Statist. Comput., 13 (1992), 1–29 | DOI | MR | Zbl

[24] Kaporin I.E., “Otsenki granits spektra dvustoronnikh yavnykh predobuslovlivanii”, Vestn. MGU. Ser. 15. Vychisl. matem. i kibernetika, 1993, no. 2, 28–42 | MR

[25] Dzhordzh A., Lyu Dzh., Chislennoe reshenie bolshikh razrezhennykh sistem uravnenii, Mir, M., 1984 | MR

[26] Eremin A.Yu., Kaporin I.E., “Vliyanie naibolshikh sobstvennykh znachenii na chislennuyu skhodimost metoda sopryazhennykh gradientov”, Chisl. metody i vopr. organizatsii vychislenii. XIII, Zap. nauchn. seminarov POMI, 248, POMI, SPb., 1998, 5–16 | MR

[27] Ashby S.F., “Minimax polynomial preconditioning for hermitian linear systems”, SIAM. J. Matrix Anal. Appl., 12:4 (1991), 766–789 | DOI | MR | Zbl