519.63 Parallel multigrid algorithms

Martynenko S. I. (Baranov Central Institute of Aviation Motor Development)

MULTIGRID TECHNIQUE, BOUNDARY VALUE PROBLEMS, PARALLELISM.


doi: 10.18698/2309-3684-2015-2-105120


The paper represents the main directions of development of the parallel classic multigrid algorithms and discusses their disadvantages. The possibility of efficient parallelization of smoothing iterations at the levels of coarse grids is shown using the Robust Multigrid Technique. Then multigrid structure is used for developing hybrid multigrid method. The paper describes estimations of speed-up and efficiency of different parallel multigrid algorithms as well as the results of numerical experiments.


[1] Vlasova E.A., Zarubin V.S., Kuvyrkin G.N. Priblizhennye metody matemati-cheskoi fiziki [Approximate methods in mathematical physics]. Zarubin V.S., Krischenko A.P., eds. Moscow, BMSTU Publ., 2001, 700 p.
[2] Galanin M.P., Savenkov E.V. Metody chislennogo analiza matematicheskikh modelei [Methods of numerical analysis of mathematical models]. Moscow, BMSTU Publ., 2010, 592 p.
[3] Trottenberg U., Oosterlee C.W., Schüller A. Multigrid. Academic Press, London, 2001.
[4] Martynenko S.I. Universalnaya mnogosetochnaya tehnologiya dlya chislen-nogo resheniya kraevyh zadach na strukturirovannyh setkah [Robust multigrid technique for solving boundary value problems on the structured grids]. Vychislitelnye metody i programmirovanie [Numerical methods and programming], 2000, vol. 1, section 1, pp. 85–104.
[5] Martynenko S.I. Computational Methods in Applied Mathematics, 2006, vol. 6, no. 4, pp. 413–435.
[6] Martynenko S.I. Matematicheskoe modelirovanie – Mathematical Modeling, 2009, vol. 21, no. 9, pp. 66–79.
[7] Martynenko S.I. International Journal of Computer Science and Mathematics, 2013, vol. 4, no. 4, pp. 309−320.
[8] Martynenko S.I. Universalnaya mnogosetochnaya tekhnologiya [Robust multigrid technique]. Moscow, Keldysh Institute of Applied Mathematic of RAS Publ., 2013, 244 p. Available at: http://library.keldysh.ru/prep\_vw.asp?pid=3715
[9] Martynenko S.I. Rasparallelivanie universalnoy mnogosetochnoy tehnologii [Deparallelization of the robust multigrid technique]. Vychislitelnye metody i programmirovanie [Numerical methods and programming], 2003, vol. 4, section 1, pp. 45–51.
[10] Martynenko S.I. Computational Methods in Applied Mathematics, 2010,
vol. 10, no. 1, pp. 87–94.
[11] Martynenko S.I. Vestnic MGTU im. N.E. Baumana. Seria Estestvennye nauki – Herald of the Bauman Moscow State Technical University. Series: Natural Sciences, 2011, no. 4, pp. 63–80.
[12] Voevodin V.V., Voevodin Vl.V. Parallelnye vychisleniya [Parallel computing]. St. Petersburg, BHV-Petersburg Publ., 2002, 608 p.
[13] Nemnyugin S.A., Stesik O.L. Parallelnoe programmirovanie dlya mnogo-protsessornyh vychislitelnyh sistem [Parallel programming for the multiproces-sor computing systems]. St. Petersburg, BHV-Petersburg Publ., 2002, 400 p.
[14] Kopysov S.P., Novikov A.K. Promezhutochnoe programmnoe obespechenie parallelnyh vychisleniy [Intermediate software for the parallel computing]. Izhevsk, Udmurtia University Publ., 2012, 140 p.
[15] Ortega J.M. Introduction to parallel and vector solution of linear systems. Plenum Press, New York, 1988. [Russian edition: Ortega Dzh. Vvedenie v parallelnye i vektornye metody resheniya lineinykh sistem. Moscow, Mir Publ., 1991, 367 p.].
[16] Zhukov V.T., Novikova N.D., Feodoritova O.B. Parallelnyi mnogosetochnyi metod dlya raznostnykh ellipticheskikh uravneniy [A parallel multigrid method for the ellip-tic difference equations]. Part I: Osnovnye komponenty algoritma [Basic compo-nents of the algorithm]. Preprint of Keldysh Institute of Applied Mathematic of RAS, 2012, no. 30, 32 p. Available at: http://library.keldysh.ru/preprint.asp?id=2012-30
[17] Antonov A.S. Parallelnoe programmirovanie s ispolzovaniem tehnologii OpenMP [Parallel programming using technology OpenMP]. Moscow, MSU Publ., 2009, 77 p.


Martynenko S. Parallel multigrid algorithms. Маthematical Modeling and Coтputational Methods, 2015, №2 (6), pp. 105-120



Download article

Колличество скачиваний: 190