Parallel iterative methods using factorized preconditioning matrices for solving elliptic equations on triangular grids

O. Yu. Milyukova

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 6, pp. 1096-1113

Résumé

Parallel analogs of the variants of the incomplete Cholesky-conjugate gradient method and the modified incomplete Cholesky-conjugate gradient method for solving elliptic equations on uniform triangular and unstructured triangular grids on parallel computer systems with the MIMD architecture are considered. The construction of parallel methods is based on the use of various variants of ordering the grid points depending on the decomposition of the computation domain. Results of the theoretic and experimental studies of the convergence rate of these methods are presented. The solution of model problems on a moderate number processors is used to examine the efficiency of the proposed parallel methods.

Bibliographie

[1] 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. Comput., 31:137 (1977), 148–162 | DOI | MR | Zbl

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

[3] Gustafsson I., “A class of first order factorization methods”, BIT, 18 (1978), 142–156 | DOI | MR | Zbl

[4] Axelsson O., Barker V. A., Finite element solution of boundary value problems. Theory and computations, Acad. Press, New York, 1984 | MR | Zbl

[5] Axelsson O., Lindskog G., “On the eigenvalue distribution of class of preconditioning methods”, Numer. Math., 48 (1986), 479–498 | DOI | MR | Zbl

[6] Kershaw D., “The incomplete Choleski-conjugate gradient method for the iterative solution of systems of linear equations”, J. Comput. Phys., 26 (1978), 43–65 | DOI | MR | Zbl

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

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

[9] Milyukova O. Yu., “Parallelnye varianty nekotorykh iteratsionnykh metodov s faktorizovannoi matritsei predobuslovlivaniya”, Zh. vychisl. matem. i matem. fiz., 41:11 (2001), 1619–1636 | MR | Zbl

[10] Milyukova O. Yu., “Parallel version of approximate factorization method for solving 2D and 3D elliptic equations”, J. Comput. Meth. in Seien. and Engng., 2:1–2 (2002), 195–200

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

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

[13] Notay Y., “DRIC: a dinamic version of the RIC method”, J. Numer. Linear Algebra with Appl., 1 (1994), 511–533 | DOI | MR

[14] Milyukova O. Yu., Popov I. V., “Parallelnye iteratsionnye metody s faktorizovannymi matritsami predobuslovlivaniya dlya resheniya diskretnykh ellipticheskikh uravnenii na nestrukturirovannoi treugolnoi setke”, Matem. modelirovanie, 15:10 (2003), 3–16 | MR | Zbl

[15] Milyukova O. Yu., “Parallel iterative methods with factored preconditioning matrices for solving discrete elliptic equations”, Parallel Comput. Fluid Dynamics (Moscow, Russia, May 13–15, 2003), Elsevier Sci. B. V., Amsterdam, 2004, 97–104 | Zbl

[16] Milyukova O. Yu., “Parallelnye varianty nekotorykh iteratsionnykh metodov s faktorizovannymi matritsami predobuslovlivaniya dlya resheniya ellipticheskikh uravnenii na nestrukturirovannykh treugolnykh setkakh”, Matem. modelirovanie, 17:2 (2005), 65–80 | Zbl

[17] Hendrickson B., Leland R., “A multilevel algorithm for partitioning graphs”, Supercom-puting'95 Proc., San Diego, CA, 1995

[18] Boldyrev C. H., Levanov E. I., Sukov C. A., Yakobovskii M. B., Obrabotka i khranenie neregulyarnykh setok bolshogo razmera na mnogoprotsessornykh sistemakh, Setochnye metody dlya kraevykh zadach i prilozheniya. Materialy IV Vseros. seminara. Kazan, 13–16 sentyabrya 2002, 33–39 pp.

[19] Yakobovskii M. V., “Obrabotka setochnykh dannykh na raspredelennykh vychislitelnykh sistemakh”, Vopr. atomnoi nauki i tekhn. Ser. Matem. modelirovanie fiz. protsessov, 2004, no. 2, 40–53

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

[21] Pascal J. F., Paul-Louis G., Mesh generation application to finite elements, Hermes Science Publs, Oxford, 2000 | MR

[22] Samarskii A. A., Nikolaev E. C., Metody resheniya setochnykh uravnenii, Nauka, M., 1978 | MR

[23] Samarskii A. A., Teoriya raznostnykh skhem, Nauka, M., 1989 | MR

[24] Milyukova O. Yu., “Parallelnyi variant obobschennogo poperemenno-treugolnogo metoda dlya resheniya ellipticheskikh uravnenii”, Zh. vychisl. matem. i matem. fiz., 38:12 (1998), 2002–2012 | MR | Zbl

[25] Marchuk G. I., Metody vychislitelnoi matematiki, Nauka, M., 1980 | MR

[26] Popov I. V., Polyakov C. B., “Postroenie adaptivnykh neregulyarnykh treugolnykh setok dlya dvumernykh mnogosvyaznykh nevypuklykh oblastei”, Matem. modelirovanie, 14:6 (2002), 25–35 | MR | Zbl

[27] Tkhir A. B., “Metod prodvinutogo fronta dlya postroeniya nestrukturirovannykh setok”, Chisl. metody i prilozh., In-t vychisl. matem. RAN, M., 1995, 15–25