Top

Computing and Visualization in Science

Published in:

06-10-2017 | Original Article

Multigrid methods with space–time concurrency

Authors: R. D. Falgout, S. Friedhoff, Tz. V. Kolev, S. P. MacLachlan, J. B. Schroder, S. Vandewalle

Published in: Computing and Visualization in Science | Issue 4-5/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the comparison of multigrid methods for parabolic partial differential equations that allow space–time concurrency. With current trends in computer architectures leading towards systems with more, but not faster, processors, space–time concurrency is crucial for speeding up time-integration simulations. In contrast, traditional time-integration techniques impose serious limitations on parallel performance due to the sequential nature of the time-stepping approach, allowing spatial concurrency only. This paper considers the three basic options of multigrid algorithms on space–time grids that allow parallelism in space and time: coarsening in space and time, semicoarsening in the spatial dimensions, and semicoarsening in the temporal dimension. We develop parallel software and performance models to study the three methods at scales of up to 16K cores and introduce an extension of one of them for handling multistep time integration. We then discuss advantages and disadvantages of the different approaches and their benefit compared to traditional space-parallel algorithms with sequential time stepping on modern architectures.

previous article On the influence of the wall shear stress vector form on hemodynamic indicators

next article Error analysis in determining the centroids of circular objects in images

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

One possibility to save on memory in the waveform relaxation approach is to subdivide the time interval into a sequence of “windows” that are treated sequentially [43]. However, there is an apparent parallel performance tradeoff with this reduction in storage requirement.

Ashby, S.F., Falgout, R.D.: A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations. Nucl. Sci. Eng. 124(1), 145–159 (1996). UCRL-JC-122359CrossRef

Bastian, P., Burmeister, J., Horton, G.: Implementation of a parallel multigrid method for parabolic partial differential equations. In: W. Hackbusch (ed.) Parallel Algorithms for PDEs, Proc. 6th GAMM Seminar Kiel, January 19–21, 1990, pp. 18–27. Vieweg, Braunschweig (1990)

Bjørhus, M.: On domain decomposition, subdomain iteration and waveform relaxation. Ph.D. thesis, Department of Mathematical Sciences, Norwegian Institute of Technology, University of Trondheim, Trondheim, Norway (1995)

Bolten, M., Moser, D., Speck, R.: A multigrid perspective on the parallel full approximation scheme in space and time. Numerical Linear Algebra with Applications pp. e2110–n/a (2017). E2110 nla.2110

Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comput. 31, 333–390 (1977)CrossRefMATHMathSciNet

Buzbee, B.L., Golub, G.H., Nielson, C.W.: On direct methods for solving Poisson’s equations. SIAM J. Numer. Anal. 7, 627–656 (1970)CrossRefMATHMathSciNet

Chartier, P., Philippe, B.: A parallel shooting technique for solving dissipative ODEs. Computing 51(3–4), 209–236 (1993)CrossRefMATHMathSciNet

Christlieb, A.J., Macdonald, C.B., Ong, B.W.: Parallel high-order integrators. SIAM J. Sci. Comput. 32(2), 818–835 (2010)CrossRefMATHMathSciNet

De Sterck, H., Manteuffel, T.A., McCormick, S.F., Olson, L.: Least-squares finite element methods and algebraic multigrid solvers for linear hyperbolic PDEs. SIAM J. Sci. Comput. 26(1), 31–54 (2004)CrossRefMATHMathSciNet

10.

Emmett, M., Minion, M.L.: Toward an efficient parallel in time method for partial differential equations. Commun. Appl. Math. Comput. Sci. 7(1), 105–132 (2012)CrossRefMATHMathSciNet

11.

Falgout, R.D., Jones, J.E.: Multigrid on massively parallel architectures. In: E. Dick, K. Riemslagh, J. Vierendeels (eds.) Multigrid Methods VI, Lecture Notes in Computational Science and Engineering, vol. 14, pp. 101–107. Springer (2000). Proceedings of the Sixth European Multigrid Conference held in Gent, Belgium, September 27–30, 1999. UCRL-JC-133948

12.

Falgout, R.D., Katz, A., Kolev, Tz.V., Schroder, J.B., Wissink, A., Yang, U.M.: Parallel time integration with multigrid reduction for a compressible fluid dynamics application. Lawrence Livermore National Laboratory (2014)

13.

Falgout, R.D., Friedhoff, S., Kolev, T.V., MacLachlan, S.P., Schroder, J.B.: Parallel time integration with multigrid. SIAM J. Sci. Comput. 36(6), C635–C661 (2014)CrossRefMATHMathSciNet

14.

Friedhoff, S., MacLachlan, S.: A generalized predictive analysis tool for multigrid methods. Numer. Linear Algebr. Appl. 22(4), 618–647 (2015)CrossRefMATHMathSciNet

15.

Gahvari, H., Baker, A., Schulz, M., Yang, U.M., Jordan, K., Gropp, W.: Modeling the performance of an algebraic multigrid cycle on HPC platforms. In: 25th ACM International Conference on Supercomputing, Tucson, AZ (2011)

16.

Gander, M.J.: 50 years of time parallel time integration. In: Carraro, T., Geiger, M., Körkel, S., Rannacher, R. (eds.) Multiple Shooting and Time Domain Decomposition, pp. 69–113. Springer, Cham (2015)

17.

Gander, M.J., Neumüller, M.: Analysis of a new space–time parallel multigrid algorithm for parabolic problems. SIAM J. Sci. Comput. 38(4), A2173–A2208 (2016)CrossRefMATHMathSciNet

18.

Gander, M.J., Stuart, A.M.: Space–time continuous analysis of waveform relaxation for the heat equation. SIAM J. Sci. Comput. 19(6), 2014–2031 (1998)CrossRefMATHMathSciNet

19.

Gander, M.J., Vandewalle, S.: Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29(2), 556–578 (2007)CrossRefMATHMathSciNet

20.

Güttel, S.: A parallel overlapping time-domain decomposition method for ODEs. Domain decomposition methods in science and engineering XX. Lect. Notes Comput. Sci. Eng, vol. 91, pp. 459–466. Springer, Heidelberg (2013)

21.

Hackbusch, W.: Parabolic Multigrid Methods. Computing Methods in Applied Sciences and Engineering. VI (Versailles, 1983), pp. 189–197. North-Holland, Amsterdam (1984)

22.

Hockney, R.W.: A fast direct solution of Poisson’s equation using Fourier analysis. J. Assoc. Comput. Mach. 12, 95–113 (1965)CrossRefMATHMathSciNet

23.

Hockney, R.W., Jesshope, C.R.: Parallel Computers: Architecture. Programming and Algorithms. Adam Hilger, Bristol (1981)MATH

24.

Horton, G.: The time-parallel multigrid method. Commun. Appl. Numer. Methods 8(9), 585–595 (1992)CrossRefMATHMathSciNet

25.

Horton, G., Knirsch, R.: A time-parallel multigrid-extrapolation method for parabolic partial differential equations. Parallel Comput. 18(1), 21–29 (1992)CrossRefMATHMathSciNet

26.

Horton, G., Vandewalle, S.: A space-time multigrid method for parabolic partial differential equations. SIAM J. Sci. Comput. 16(4), 848–864 (1995)CrossRefMATHMathSciNet

27.

Horton, G., Vandewalle, S., Worley, P.: An algorithm with polylog parallel complexity for solving parabolic partial differential equations. SIAM J. Sci. Comput. 16(3), 531–541 (1995)CrossRefMATHMathSciNet

28.

hypre: High performance preconditioners. http://www.llnl.gov/CASC/hypre/

29.

Keller, H.B.: Numerical Methods for Two-Point Boundary-Value Problems. Blaisdell Publishing Co. Ginn and Co., Waltham (1968)

30.

Kogge, P.M.: A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. Comput. C 22(8), 786–793 (1973)

31.

Lelarasmee, E., Ruehli, A.E., Sangiovanni-Vincentelli, A.L.: The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE CAD 1(3), 131–145 (1982)CrossRef

32.

Lions, J.L., Maday, Y., Turinici, G.: Résolution d’EDP par un schéma en temps “pararéel”. C. R. Acad. Sci. Paris Sér. I Math. 332(7), 661–668 (2001)CrossRefMATHMathSciNet

33.

Lubich, C., Ostermann, A.: Multigrid dynamic iteration for parabolic equations. BIT 27(2), 216–234 (1987)CrossRefMATHMathSciNet

34.

Maday, Y., Rønquist, E.M.: Parallelization in time through tensor-product space–time solvers. C. R. Math. Acad. Sci. Paris 346(1–2), 113–118 (2008)CrossRefMATHMathSciNet

35.

Minion, M.L., Williams, S.A.: Parareal and spectral deferred corrections. In: T.E. Simos (ed.) Numerical Analysis and Applied Mathematics, No. 1048 in AIP Conference Proceedings, pp. 388–391. AIP (2008)

36.

Minion, M.L., Speck, R., Bolten, M., Emmett, M., Ruprecht, D.: Interweaving PFASST and parallel multigrid. SIAM J. Sci. Comput. 37(5), S244–S263 (2015)CrossRefMATHMathSciNet

37.

Miranker, W.L., Liniger, W.: Parallel methods for the numerical integration of ordinary differential equations. Math. Comput. 21, 303–320 (1967)CrossRefMATHMathSciNet

38.

Nievergelt, J.: Parallel methods for integrating ordinary differential equations. Commun. ACM 7, 731–733 (1964)CrossRefMATHMathSciNet

39.

Ries, M., Trottenberg, U.: MGR-ein blitzschneller elliptischer Löser. Tech. Rep. Preprint 277 SFB 72, Universität Bonn (1979)

40.

Ries, M., Trottenberg, U., Winter, G.: A note on MGR methods. J. Linear Algebr. Appl. 49, 1–26 (1983)CrossRefMATHMathSciNet

41.

Sheen, D., Sloan, I.H., Thomée, V.: A parallel method for time discretization of parabolic equations based on Laplace transformation and quadrature. IMA J. Numer. Anal. 23(2), 269–299 (2003)CrossRefMATHMathSciNet

42.

Speck, R., Ruprecht, D., Emmett, M., Bolten, M., Krause, R.: A space-time parallel solver for the three-dimensional heat equation. In: Bader, M., Bode, A., Bungartz, H.-J., Gerndt, M., Joubert, G.R., Peter, F. (eds.) Parallel Computing: Accelerating Computational Science and Engineering (CSE), Advances in Parallel Computing, vol. 25, pp. 263–272. IOS Press (2014)

43.

Vandewalle, S.G., Van de Velde, E.F.: Space-time concurrent multigrid waveform relaxation. Ann. Numer. Math. 1(1–4), 347–360 (1994). Scientific computation and differential equations (Auckland, 1993)

44.

Vandewalle, S., Horton, G.: Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods. Computing 54(4), 317–330 (1995)CrossRefMATHMathSciNet

45.

Vandewalle, S., Piessens, R.: Efficient parallel algorithms for solving initial-boundary value and time-periodic parabolic partial differential equations. SIAM J. Sci. Stat. Comput. 13(6), 1330–1346 (1992)CrossRefMATHMathSciNet

46.

Weinzierl, T., Köppl, T.: A geometric space-time multigrid algorithm for the heat equation. Numer. Math. Theory Methods Appl. 5(1), 110–130 (2012)MATHMathSciNet

47.

XBraid: Parallel multigrid in time. http://llnl.gov/casc/xbraid

Title: Multigrid methods with space–time concurrency
Authors: R. D. Falgout
S. Friedhoff
Tz. V. Kolev
S. P. MacLachlan
J. B. Schroder
S. Vandewalle
Publication date: 06-10-2017
Publisher: Springer Berlin Heidelberg
Published in: Computing and Visualization in Science / Issue 4-5/2017
Print ISSN: 1432-9360
Electronic ISSN: 1433-0369
DOI: https://doi.org/10.1007/s00791-017-0283-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4-5/2017

On the influence of the wall shear stress vector form on hemodynamic indicators

Characterizing groundwater flow in the fractured rock at Äspö, Sweden

The spherical design algorithm in the numerical simulation of biological tissues with statistical fibre-reinforcement

Error analysis in determining the centroids of circular objects in images

Premium Partner