More Web Proxy on the site http://driver.im/

research-article

Parallel Time Integration with Multigrid

Authors:

S. P. MacLachlan,

J. B. SchroderAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 36, Issue 6

Pages C635 - C661

https://doi.org/10.1137/130944230

Published: 01 January 2014 Publication History

Abstract

We consider optimal-scaling multigrid solvers for the linear systems that arise from the discretization of problems with evolutionary behavior. Typically, solution algorithms for evolution equations are based on a time-marching approach, solving sequentially for one time step after the other. Parallelism in these traditional time-integration techniques is limited to spatial parallelism. However, current trends in computer architectures are leading toward systems with more, but not faster, processors. Therefore, faster compute speeds must come from greater parallelism. One approach to achieving parallelism in time is with multigrid, but extending classical multigrid methods for elliptic operators to this setting is not straightforward. In this paper, we present a nonintrusive, optimal-scaling time-parallel method based on multigrid reduction (MGR). We demonstrate optimality of our multigrid-reduction-in-time algorithm (MGRIT) for solving diffusion equations in two and three space dimensions in numerical experiments. Furthermore, through both parallel performance models and actual parallel numerical results, we show that we can achieve significant speedup in comparison to sequential time marching on modern architectures.

References

[1]

hypre: High Performance Preconditioners, http://www.llnl.gov/casc/hypre/.

[2]

P. Amodio and L. Brugnano, Parallel solution in time of ODEs: Some achievements and perspectives, Appl. Numer. Math., 59 (2009), pp. 424--435.

[3]

S. F. Ashby and R. D. Falgout, A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations, Nuclear Sci. Engrg., 124 (1996), pp. 145--159.

[4]

R. E. Bank and R. K. Smith, The incomplete factorization multigraph algorithm, SIAM J. Sci. Comput., 20 (1999), pp. 1349--1364.

[5]

R. E. Bank and R. K. Smith, An algebraic multilevel multigraph algorithm, SIAM J. Sci. Comput., 23 (2002), pp. 1572--1592.

[6]

A. Brandt, Multi--level adaptive solutions to boundary--value problems, Math. Comp., 31 (1977), pp. 333--390.

[7]

J. Bulin, Large-Scale Time Parallelization For Molecular Dynamics Problems, Master's thesis, Royal Institute of Technology, Stockholm, Sweden, 2013.

[8]

A. J. Christlieb, R. D. Haynes, and B. W. Ong, A parallel space-time algorithm, SIAM J. Sci. Comput., 34 (2012), pp. C233--C248.

[9]

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

[10]

X. Dai and Y. Maday, Stable parareal in time method for first- and second-order hyperbolic systems, SIAM J. Sci. Comput., 35 (2013), pp. A52--A78.

[11]

R. D. Falgout and J. E. Jones, Multigrid on massively parallel architectures, in Multigrid Methods VI, E. Dick, K. Riemslagh, and J. Vierendeels, eds., Lect. Notes Comput. Sci. Eng. 14, Springer-Verlag, Berlin, 2000, pp. 101--107.

[12]

H. Foerster, K. Stüben, and U. Trottenberg, Nonstandard multigrid techniques using checkered relaxation and intermediate grids, in Elliptic Problem Solvers, M. Schulz, ed., Academic Press, New York, 1981, pp. 285--300.

[13]

H. Gahvari, A. Baker, M. Schulz, U. Meier Yang, K. Jordan, and W. Gropp, Modeling the performance of an algebraic multigrid cycle on HPC platforms, in Proceedings of the 25th ACM International Conference on Supercomputing, Tucson, AZ, 2011, pp. 172--181.

[14]

M. J. Gander and S. Güttel, PARAEXP: A parallel integrator for linear initial-value problems, SIAM J. Sci. Comput., 35 (2013), pp. C123--C142.

[15]

M. J. Gander and E. Hairer, Nonlinear convergence analysis for the parareal algorithm, in Domain Decomposition Methods in Science and Engineering XVII, U. Langer, M. Discacciati, D. E. Keyes, O. B. Widlund, and W. Zulehner, eds., Lect. Notes Comput. Sci. Eng. 60, Springer, Berlin, Heidelberg, 2008, pp. 193--200.

[16]

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

[17]

I. Garrido, B. Lee, G. E. Fladmark, and M. S. Espedal, Convergent iterative schemes for time parallelization, Math. Comp., 75 (2006), pp. 1403--1428.

[18]

C. W. Gear, Parallel methods for ordinary differential equations, Calcolo, 25 (1988), pp. 1--20.

[19]

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

[20]

G. Horton and R. Knirsch, A space-time multigrid method for parabolic partial differential equations, Parallel Comput., 18 (1992), pp. 21--29.

[21]

G. Horton and S. Vandewalle, A space-time multigrid method for parabolic partial differential equations, SIAM J. Sci. Comput., 16 (1994), pp. 848--864.

[22]

K. R. Jackson, A survey of parallel numerical methods for initial value problems for ordinary differential equations, IEEE Trans. Magnetics, 27 (1991), pp. 3792--3797.

[23]

D. Kamowitz and S. V. Parter, On MGR[$\nu$] multigrid methods, SIAM J. Numer. Anal., 24 (1987), pp. 366--381.

[24]

Z. Li, Y. Saad, and M. Sosonkina, pARMS: A parallel version of the algebraic recursive multilevel solver, Numer. Linear Algebra Appl., 10 (2003), pp. 485--509.

[25]

J. L. Lions, Y. Maday, and G. Turinici, Résolution d'EDP par un schéma en temps pararéel, C. R. Acad. Sci. Paris Sér. I Math, 332 (2001), pp. 661--668.

[26]

S. MacLachlan, T. Manteuffel, and S. McCormick, Adaptive reduction-based AMG, Numer. Linear Algebra Appl., 13 (2006), pp. 599--620.

[27]

S. MacLachlan and Y. Saad, Greedy coarsening strategies for nonsymmetric problems, SIAM J. Sci. Comput., 29 (2007), pp. 2115--2143.

[28]

Y. Maday, The “parareal in time” algorithm, in Sub-Structuring Techniques and Domain Decomposition Methods, F. Magoulès, ed., Comput. Sci. Engrg. Tech., Saxe-Coburg, Stirlingshire, UK, 2010, ch. 2, pp. 19--44.

[29]

C. Mense and R. Nabben, On algebraic multi-level methods for non-symmetric systems---comparison results, Linear Algebra Appl., 429 (2008), pp. 2567--2588.

[30]

C. Mense and R. Nabben, On algebraic multilevel methods for non-symmetric systems---convergence results, Electron. Trans. Numer. Anal., 30 (2008), pp. 323--345.

[31]

M. L. Minion, A hybrid parareal spectral deferred corrections method, Commun. Appl. Math. Comput. Sci., 5 (2010), pp. 265--301.

[32]

M. L. Minion and S. A. Williams, Parareal and spectral deferred corrections, in Numerical Analysis and Applied Mathematics, T. E. Simos, ed., AIP Conference Proceedings 1048, AIP, Melville, NY, 2008, pp. 388--391.

[33]

J. Nievergelt, Parallel methods for integrating ordinary differential equations, Comm. ACM, 7 (1964), pp. 731--733.

[34]

Y. Notay, Algebraic multigrid and algebraic multilevel methods: A theoretical comparison, Numer. Linear Algebra Appl., 12 (2005), pp. 419--451.

[35]

S. V. Parter, On an estimate for the three-grid MGR multigrid method, SIAM J. Numer. Anal., 24 (1987), pp. 1032--1045.

[36]

M. Ries and U. Trottenberg, MGR-ein blitzschneller elliptischer löser, Tech. report, Preprint 277 SFB 72, Universität Bonn, Bonn, Germany, 1979.

[37]

M. Ries, U. Trottenberg, and G. Winter, A note on MGR methods, Linear Algebra Appl., 49 (1983), pp. 1--26.

[38]

D. Ruprecht and R. Krause, Explicit parallel-in-time integration of a linear acoustic-advection system, Comput. Fluids, 59 (2012), pp. 72--83.

[39]

Y. Saad and B. Suchomel, ARMS: An algebraic recursive multilevel solver for general sparse linear systems, Numer. Linear Algebra Appl., 9 (2002), pp. 359--378.

[40]

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

[41]

R. Speck, D. Ruprecht, M. Emmett, M. Minion, M. Bolten, and R. Krause, A multi-level spectral deferred correction method, preprint, http://arxiv.org/abs/1307.1312, 2013.

[42]

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

[43]

T. Weinzierl and T. Köppl, A geometric space-time multigrid algorithm for the heat equation, Numer. Math. Theory Methods Appl., 5 (2012), pp. 110--130.

[44]

D. E. Womble, A time-stepping algorithm for parallel computers, SIAM J. Sci. Stat. Comput., 11 (1990), pp. 824--837.

Cited By

Caldas Steinstraesser JPeixoto PSchreiber M(2024)Parallel-in-time integration of the shallow water equations on the rotating sphere using Parareal and MGRITJournal of Computational Physics10.1016/j.jcp.2023.112591496:COnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.jcp.2023.112591
Verhelst HDen Besten JMöller M(2024)An adaptive parallel arc-length methodComputers and Structures10.1016/j.compstruc.2024.107300296:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.compstruc.2024.107300
Zhang JXu G(2024)A novel α-absolute value preconditioner for all-at-once systems from heat equationsComputers & Mathematics with Applications10.1016/j.camwa.2024.04.030165:C(196-204)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.camwa.2024.04.030
Show More Cited By

Recommendations

Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
^† Special Section: 2016 Copper Mountain Conference

The need for parallelism in the time dimension is being driven by changes in computer architectures, where performance increases are now provided through greater concurrency, not faster clock speeds. This creates a bottleneck for sequential time marching ...
Efficient Multigrid Reduction-in-Time for Method-of-Lines Discretizations of Linear Advection
Abstract
Parallel-in-time methods for partial differential equations (PDEs) have been the subject of intense development over recent decades, particularly for diffusion-dominated problems. It has been widely reported in the literature, however, that many ...
Multigrid Methods for Second Order Hamilton--Jacobi--Bellman and Hamilton--Jacobi--Bellman--Isaacs Equations
^† Special Section: 2012 Copper Mountain Conference

We propose multigrid methods for solving the discrete algebraic equations arising from the discretization of the second order Hamilton--Jacobi--Bellman (HJB) and Hamilton--Jacobi--Bellman--Isaacs (HJBI) equations. We propose a damped-relaxation method as a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 36, Issue 6

2014

572 pages

ISSN:1064-8275

DOI:10.1137/sjoce3.36.6

Issue’s Table of Contents

© 2014, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2014

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Caldas Steinstraesser JPeixoto PSchreiber M(2024)Parallel-in-time integration of the shallow water equations on the rotating sphere using Parareal and MGRITJournal of Computational Physics10.1016/j.jcp.2023.112591496:COnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.jcp.2023.112591
Verhelst HDen Besten JMöller M(2024)An adaptive parallel arc-length methodComputers and Structures10.1016/j.compstruc.2024.107300296:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.compstruc.2024.107300
Zhang JXu G(2024)A novel α-absolute value preconditioner for all-at-once systems from heat equationsComputers & Mathematics with Applications10.1016/j.camwa.2024.04.030165:C(196-204)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.camwa.2024.04.030
Lin XWu S(2024)A parallel-in-time preconditioner for Crank–Nicolson discretization of a parabolic optimal control problemJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116106451:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116106
Li G(2024)Wavelet-based Edge Multiscale Parareal Algorithm for subdiffusion equations with heterogeneous coefficients in a large time domainJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115608440:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.cam.2023.115608
Reynolds DGardner DWoodward CChinomona R(2023)ARKODE: A Flexible IVP Solver Infrastructure for One-step MethodsACM Transactions on Mathematical Software10.1145/359463249:2(1-26)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1145/3594632
Bolten MFriedhoff SHahne J(2023)Task graph-based performance analysis of parallel-in-time methodsParallel Computing10.1016/j.parco.2023.103050118:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.parco.2023.103050
Cheng TYang HHuang JYang C(2023)Nonlinear parallel-in-time simulations of multiphase flow in porous mediaJournal of Computational Physics10.1016/j.jcp.2023.112515494:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.jcp.2023.112515
Nguyen HTsai R(2023)Numerical wave propagation aided by deep learningJournal of Computational Physics10.1016/j.jcp.2022.111828475:COnline publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1016/j.jcp.2022.111828
Li SXie LZhou L(2023)Convergence analysis of space-time domain decomposition method for parabolic equations▪Computers & Mathematics with Applications10.1016/j.camwa.2022.08.012139:C(209-215)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.camwa.2022.08.012
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents