Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods

O. Yu. Milyukova

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 5, pp. 711-729

Résumé

Parallel versions of the stabilized second-order incomplete triangular factorization conjugate gradient method in which the reordering of the coefficient matrix corresponding to the ordering based on splitting into subdomains with separators are considered. The incomplete triangular factorization is organized using the truncation of fill-in “by value” at internal nodes of subdomains, and “by value” and “by positions” on the separators. This approach is generalized for the case of constructing a parallel version of preconditioning the second-order incomplete LU factorization for nonsymmetric diagonally dominant matrices with. The reliability and convergence rate of the proposed parallel methods is analyzed. The proposed algorithms are implemented using MPI, results of solving benchmark problems with matrices from the collection of the University of Florida are presented.

Bibliographie

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

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

[3] Milyukova O. Yu., “Nekotorye parallelnye iteratsionnye metody s faktorizovannymi matritsami predobuslovlivaniya dlya resheniya ellipticheskikh uravnenii na treugolnykh setkakh”, Zh. vychisl. matem. i matem. fiz., 46:6 (2006), 1096–1112 | MR

[4] Meijerink J. A., van der Vorst H. A., “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] Gustafsson I., “A Class of First Order Factorization Methods”, BIT, 18 (1978), 142–156 | DOI | MR | Zbl

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

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

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

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

[10] Kaporin I. E., “High quality preconditionings of a general symmetric positive definite matrix based on its $U^{\mathrm{T}}U+U^{\mathrm{T}}R+R^{\mathrm{T}}U$-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

[11] 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

[12] Kaporin I. E., Milyukova O. Yu., “Massivno-parallelnyi algoritm predobuslovlennogo metoda sopryazhennykh gradientov dlya chislennogo resheniya sistem lineinykh algebraicheskikh uravnenii”, Sb. trudov otdela problem prikl. optimizatsii VTs RAN, ed. V. G. Zhadan, Iz-vo VTs RAN, M., 2011, 32–49

[13] Kaporin I. E., Milyukova O. Yu., Bartenev Yu. G., “Massivno-parallelnye predobuslovlennye metody resheniya SLAU s razrezhennymi matritsami bolshogo razmera”, Vysokoproizvoditelnye parallelnye vychisleniya na klasternykh sistemakh, Materialy XIII Vserossiiskoi konferentsii (N. Novgorod, 14–16 noyabrya 2013 g.), ed. V. P. Gergel, Izd-vo Nizhegorodskogo gos. un-ta, N. Novgorod, 2013, 151–156

[14] Kaporin I. E., Milyukova O. Yu., “Predobuslovlivanie iteratsionnykh metodov dlya effektivnogo massivno-parallelnogo resheniya sistem lineinykh algebraicheskikh uravnenii”, Supervychisleniya i matematicheskoe modelirovanie, Tr. XIII Mezhdunar. seminara (3–7 oktyabrya 2011 g., Sarov, 2012), 243–252

[15] Bogachev K. Yu., Zhabitskii Ya. V., “Metod Kaporina–Konshina parallelnoi realizatsii blochnykh predobuslovlivatelei dlya nesimmetrichnykh matrits v zadachakh filtratsii mnogokomponentnoi smesi v poristoi srede”, Vestn. Mosk. un-ta. Ser. Matem. Mekhan., 2010, no. 1, 46–52 | MR

[16] Kharchenko S. A., “Vliyanie rasparallelivaniya vychislenii s poverkhnostnymi mezhprotsessornymi granitsami na masshtabiruemost parallelnogo iteratsionnogo algoritma resheniya sistem lineinykh uravnenii na primere uravnenii vychislitelnoi gidrodinamiki”, Parallelnye vychislitelnye tekhnologii, Materialy Mezhdunar. nauchnoi konf. PaVT'2008 (S.-Peterburg, 28 yanvarya–1 fevralya 2008 g.), Izd. YuUrGU, Chelyabinsk, 2008, 494–499

[17] Konshin I. N., Kharchenko S. A., Skvoznoi parallelnyi algoritm postroeniya nepolnogo treugolnogo razlozheniya vtorogo poryadka tochnosti s dinamicheskim vyborom dekompozitsii oblasti i uporyadocheniya, Izd. YuUrGU, Chelyabinsk, 2008, 491–494

[18] Yakushev V. L., Simbirkin V. N., Filimonov A. V., Novikov P. A., Konshin I. N., Sushko G. B., Kharchenko S. A., “Reshenie plokhoobuslovlennykh simmetrichnykh SLAU dlya zadach stroitelnoi mekhaniki parallelnymi iteratsionnymi metodami”, Vestn. Nizhegorodskogo un-ta, 2012, no. 4(1), 238–246

[19] Karypis G., Kumar V., “Parallel Threshold-based ILU Factorization”, Proc. 1997 ACM/IEEE conference on Supercomputing, Supercomputing'97, IEEE, Minnesota, 1997, 28 pp.

[20] Milyukova O. Yu., “Parallelnye varianty metoda nepolnogo treugolnogo razlozheniya vtorogo poryadka sopryazhennykh gradientov na osnove ispolzovaniya spetsialnogo pereuporyadocheniya matritsy koeffitsientov”, Preprinty IPM im. M. V. Keldysha, 2014, 052, 32 pp. http://keldysh.ru/papers/2014/prep2014_52.pdf | Zbl

[21] Milyukova O. Yu., “Sochetanie chislovykh i strukturnykh podkhodov k postroeniyu nepolnogo treugolnogo razlozheniya vtorogo poryadka v parallelnykh algoritmakh predobuslovlennogo metoda sopryazhennykh gradientov”, Preprinty IPM im. M. V. Keldysha, 2015, 010, 32 pp. http://keldysh.ru/papers/2015/prep2015_10.pdf | Zbl

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

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

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

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

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

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

[28] Van der Vorst H. A., “Bi-CGStab: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems”, SIAM J. Sci. Statist. Comput., 13 (1992), 631–644 | DOI | MR | Zbl

[29] Knight P., “The Sinkhorn–Knopp algorithm: convergence and applications”, SIAM J. Matrix. Anal. Appl., 30 (2008), 261–275 | DOI | MR | Zbl

[30] Kaporin I. E., Konshin I. N., Optimization of Matrix Scaling in CGSOL code, NeurOK Techsoft Rept., June 2003

[31] Kershaw D. S., “On the problem of unstable pivots in the incomplete $LU$-conjugate gradient method”, J. Comp. Phys., 38:1 (1980), 114–123 | DOI | MR | Zbl

[32] Pisanetski S., Tekhnologiya razrezhennykh matrits, Mir, M., 1988, 410 pp.

[33] Kaporin I. E., “Ispolzovanie polinomov Chebysheva i priblizhennogo obratnogo treugolnogo razlozheniya dlya predobuslovlivaniya metoda sopryazhennykh gradientov”, Zh. vychisl. matem. i matem. fiziki, 52:2 (2012), 1–26

[34] Yakobovskii M. V., “Inkrementnyi algoritm dekompozitsii grafov”, Vestn. Nizhegorodskogo un-ta. Seriya “Matem. modelirovanie i optimalnoe upravlenie”, 2005, no. 1(28), 243–250

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