About one parallel version of the $2^{\text{nd}}$ order incomplete triangular factorization

O. Yu. Milyukova

Matematičeskoe modelirovanie, Tome 28 (2016) no. 12, pp. 107-121.

Résumé

One parallel version of the stabilized $2^{\text{nd}}$ order incomplete triangular factorization is considered as preconditioner for the conjugate gradient method. This parallel version is based on the reordering of the matrix used of certain domain decomposition type splitting with separators. The incomplete factorization is organized using the truncation of fill-in “by value” within the subdomains and “by position” and “by value” at the separators. Non-failure operation of the considered method is theoretically proved, non-failure operation and convergence speed of the parallel method are numerically investigated. For an MPI implementation of the iterative linear solver, numerical results are given obtained for matrices from the University of Florida collection.

Détail

Keywords: iterative linear solvers, incomplete triangular factorization, parallel preconditioning.
Mots-clés : sparse matrices

Bibliographie

[1] Dzh. Ortega, Vvedenie v parallelnye i vektornye metody resheniia lineinykh system, Mir, M., 1991

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

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

[4] J. A. Meijerink, 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:137 (1977), 148–162 | MR | Zbl

[5] I. Gustafsson, “A Class of First Order Factorization Methods”, BIT, 18 (1978), 142–156 | DOI | MR | Zbl

[6] O. Axelsson, “A generalazed SSOR method”, BIT, 13 (1972), 443–467 | DOI | MR

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

[8] I. E. Kaporin, “High quality preconditionings of a general symmetric positive definite matrix based on its $U^TU+U^TR+R^TU$-decomposition”, Num. 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

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

[10] I. E. Kaporin, O. Iu. Miliukova, “Massivno-parallelnyi algoritm predobuslovlennogo metoda sopriazhennykh gradientov dlia chislennogo resheniia sistem lineinykh algebraicheskikh uravnenii”, Sb. trudov VTs RAN, ed. V. G. Zhadan, Iz-vo VTs RAN, M., 2011, 32–49

[11] S. A. Kharchenko, “Vliianie rasparallelivaniia vychislenii c poverkhnostnymi mezhprotsessornymi granitsami na masshtabiruemost parallelnogo iteratsionnogo algoritma resheniia lineinykh uravnenii vychislitelnoi gidrodinamiki”, Parallelnye vychislitelnye tekhnologii, Materialy Mezhdunar. nauchnoi konferentsii PaVT'2008 (S.-Peterburg, 2008), Izd. IUUrGU, Cheliabinsk, 2008, 494–499

[12] V. L. Iakushev, V. N. Simbirkin, A. V. Filimonov, P. A. Novikov, I. N. Konshin, G. B. Sushko, S. A. Kharchenko, “Reshenie plokhoobuslovlennykh simmetrichnykh SLAU dlia zadach stroitelnoi mekhaniki parallelnymi iteratsionnymi metodami”, Vestnik Nizhegorodskogo universiteta im. N. I. Lobashevskogo, 2012, no. 4(1), 238–246

[13] O. Yu. Milyukova, “Parallel versions of the order incomplete triangular factorization preconditioned conjugate gradient method using special matrix reordering”, Keldysh Institute preprints, 2014, 052, 32 pp. | Zbl

[14] O. Yu. Milyukova, “Combining incomplete factorization strategies “by value” and “by position” for the order incomplete triangular factorization in parallel algorithms for the preconditioned conjugate gradient method”, Keldysh Institute preprints, 2015, 10, 32 pp.

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

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

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

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

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

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

[21] I. E. Kaporin, “Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method”, Comp. Math. Math. Phys., 52:2 (2012), 169–193 | DOI | MR | Zbl

[22] M. V. Iakobovskii, “Inkrementnyi algoritm dekompozitsii grafov”, Vestnik Nizhegorodskogo universiteta im. N. I. Lobashevskogo. Seriia “Matematicheskoe modelirovanie i optimalnoe upravlenie”, 2005, no. 1(28), 243–250

[23] E. N. Golovchenko, “Parallelnyi paket dekompozitsii bolshikh setok”, Matemamicheskoe modelirovanie, 23:10 (2011), 3–18