Abstract
In the past few years, the number of processor cores of top ranked supercomputers has increased drastically. It is challenging to design efficient parallel algorithms that offer such a high degree of parallelism, especially for certain time-dependent problems because of the sequential nature of “time”. To increase the degree of parallelization, some parallel-in-time algorithms have been developed. In this paper, we give an overview of some recently introduced parallel-in-time methods, and present in detail the class of space-time Schwarz methods, including the standard and the restricted versions, for solving parabolic partial differential equations. Some numerical experiments carried out on a parallel computer with a large number of processor cores for three-dimensional problems are given to show the parallel scalability of the methods. In the end of the paper, we provide a comparison of the parallel-in-time algorithms with a traditional algorithm that is parallelized only in space.
Similar content being viewed by others
References
Al-Khaleel, M.D., Gander, M.J., Ruehli, A.E.: Optimization of transmission conditions in waveform relaxation techniques for RC circuits. SIAM J. Numer. Anal. 52, 1076–1101 (2014)
Badia, S., Olmand, M.: Space-time balancing domain decomposition. SIAM J. Sci. Comput. 39, C194–C213 (2017)
Bal, G.: On the convergence and the stability of the parareal algorithm to solve partial differential equations, in Domain Decomposition Methods in Science and Engineering. In: R. Kornhuber, R. H. W. Hoppe, D. E. Keyes, J. Periaux, O. Pironneau, and J. Xu, (eds)., vol. 40, SIAM, Springer, Berlin, 425–432 (2005)
Bal, G., Maday, Y.: A “parareal” time discretization for non-linear PDE’s with application to the pricing of an American put. In: Recent developments in domain decomposition methods (Zürich, 2001), 189–202, Lect. Notes Comput. Sci. Eng., 23, Springer, Berlin (2002)
Balay, S., Abhyankar, S., Adams, M. F., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Eijkhout, V., Kaushik, D., Knepley, M. G., McInnes, L. C., Gropp, W. D., Rupp, K., Smith, B. F., Zampini, S., Zhang, H.: PETSc Users Manual, Technical report ANL 95/11-Revision 3.7. Argonne National Laboratory, Argonne, IL, (2018)
Bellen, A., Jackiewicz, Z., Zennaro, M.: Time-point relaxation Runge–Kutta methods for ordinary differential equations. J. Comput. Appl. Math. 45, 121–137 (1993)
Bennequin, D., Gander, M.J., Halpern, L.: A homographic best approximation problem with application to optimized Schwarz waveform relaxation. Math. Comp. 78, 185–223 (2009)
Beyene, W.T.: Application of multilinear and waveform relaxation methods for efficient simulation of interconnect-dominated nonlinear networks. IEEE Trans. Adv. Packag. 31, 637–648 (2008)
Bjorhus, M., Stuart, A.M.: Waveform relaxation as a dynamical system. Math. Comp. 66, 1101–1117 (1997)
Bolten, M., Moser, D., Speck, R.: A multigrid perspective on the parallel full approximation scheme in space and time. Numer. Linear Algebra Appl. 24, e2110 (2017)
Burrage, K.: Parallel and sequential methods for ordinary differential equations. Oxford Science Publications, New York (1995)
Cai, X.-C., Sarkis, M.: A restricted additive Schwarz preconditioner for general sparse linear systems. SIAM J. Sci. Comput. 21, 792–797 (1999)
Cong, C., Cai, X.-C., Gustafson, K.: Implicit space-time domain decomposition methods for stochastic parabolic partial differential equations. SIAM J. Sci. Comput. 36, C1–C24 (2014)
Dai, X., Maday, Y.: Stable parareal in time method for first- and second-order hyperbolic systems. SIAM J. Sci. Comput. 35, A52–A78 (2013)
Deng, X., Cai, X.-C., Zou, J.: A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Probl. Imaging 9, 1069–1091 (2015)
Deng, X., Cai, X.-C., Zou, J.: Two-level space-time domain decomposition methods for three-dimensional unsteady inverse source problems. J. Sci. Comput. 67, 860–882 (2016)
Dobrev, V.A., Kolev, T.Z., Petersson, N.A., Schroder, J.B.: Two-level convergence theory for multigrid reduction in time (MGRIT). SIAM J. Sci. Comput. 39, S501–S527 (2017)
Du, X.H., Sarkis, M., Schaerer, C.F., Szyld, D.B.: Inexact and truncated parareal-in-time Krylov subspace methods for parabolic optimal control problems. Electron. Trans. Numer. Anal. 40, 36–57 (2013)
Falgout, R.D., Friedho, S., Kolev, T.Z.V., Maclachlan, S.P., Schroder, J.B.: Parallel time integration with multigrid. SIAM J. Sci. Comput. 36, C635–C661 (2014)
Falgout, R.D., Friedho, S., Kolev, T.Z.V., MacLachlan, S.P., Schroder, J.B., Vandewalle, S.: Multigrid methods with space-time concurrency. Comput. Visual. Sci. 18, 123–143 (2017)
Falgout, R.D., Manteuffel, T.A., O’Neill, B., Schroder, J.B.: Multigrid reduction in time for nonlinear parabolic problems: a case study. SIAM J. Sci. Comput. 39, S298–S322 (2017)
Farhat, C., Chandesris, M.: Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications. Internat. J. Numer. Methods Eng. 58, 1397–1434 (2003)
Frommer, A., Szyld, D.B.: An algebraic convergence theory for restricted additive Schwarz methods using weighted max norms. SIAM J. Numer. Anal. 39, 463–479 (2001)
Gander, M.J.: A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations. Numer. Linear Algebra Appl. 6, 125–145 (1999)
Gander, M.J.: Optimized schwarz methods. SIAM J. Numer. Anal. 44, 699–731 (2006)
Gander, M.J.: 50 years of time parallel time integration. Multiple shooting and time domain decomposition methods, 69-113, Contrib. Math. Comput. Sci. 9, Springer, Cham (2015)
Gander, M.J., Neumüller, M.: Analysis of a new space-time parallel multigrid algorithm for parabolic problems. SIAM J. Sci. Comput. 38, A2173–A2208 (2016)
Gander, M.J., Stuar, A.M.: Space-time continuous analysis of waveform relaxation for the heat equation. SIAM J. Sci. Comput. 19, 2014–2031 (1998)
Gander, M.J., Vandewalle, S.: Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29, 556–578 (2007)
Giladi, E., Keller, H.B.: Space-time domain decomposition for parabolic problems. Numer. Math. 93, 279–313 (2002)
Hackbusch, W.: Parabolic multigrid methods. Comput. Methods Appl. Sci. Eng. VI (Versailles, 1983), North-Holland, Amsterdam, 189–197 (1984)
Halpern, L., Japhet, C., Szeftel, J.: Optimized Schwarz waveform relaxation and discontinuous Galerkin time stepping for heterogeneous problems. SIAM J. Numer. Anal. 50, 2588–2611 (2012)
Horton, G.: The time-parallel multigrid method. Comm. Appl. Numer. Methods. 8, 585–595 (1992)
Horton, G., Vandewalle, S.: A space-time multigrid method for parabolic partial differential equations. SIAM J. Sci. Comput. 16, 848–864 (1995)
Horton, G., Vandewalle, S., Worley, P.: An algorithm with polylog parallel complexity for solving parabolic partial differential equations. SIAM J. Sci. Comput. 16, 531–541 (1995)
Jeltsch, R., Pohl, B.: Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput. 16, 40–49 (1995)
Jiang, Y.-L., Chen, R.M.M., Wing, O.: Convergence analysis of waveform relaxation for nonlinear differential-algebraic equations of index one. IEEE Trans. Circuits Syst. I. Fund. Theory Appl. 47, 1639–1645 (2000)
Lelarasmee, E., Ruehli, A. E., Sangiovanni-Vincentelli, A. L.: The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Trans. CAD of ICAS, CAD-1. 131–145 (1982)
Li, S., Cai, X.-C.: Convergence analysis of two-level space-time additive Schwarz method for parabolic equations. SIAM J. Numer. Anal. 53, 2727–2751 (2015)
Li, S., Shao, X., Cai, X.-C.: Multilevel space-time additive Schwarz methods for parabolic equations. SIAM J. Sci. Comput. 40, A3012–A3037 (2018)
Lions, J.-L., Maday, Y., Turinici, G.: Résolution d’EDP par un schéma en temps “pararéel”. Comptes Rendus de l’Académie des Sciences. Série I. Mathmatique 332, 661–668 (2001)
Lubich, C., Ostermann, A.: Multigrid dynamic iteration for parabolic equations. BIT 27, 216–234 (1987)
Maday, Y., Salomon, J., Turinici, G.: Monotonic parareal control for quantum systems. SIAM J. Numer. Anal. 45, 2468–2482 (2007)
Mathew, T.P., Sarkis, M., Schaerer, C.E.: Analysis of block parareal preconditioners for parabolic optimal control problems. SIAM J. Sci. Comput. 32, 1180–1200 (2010)
Miekkala, U., Nevanlinna, O.: Convergence of dynamic iteration methods for initial value problem. SIAM J. Sci. Stat. Comput. 8, 459–482 (1987)
Minion, M.L.: A hybrid parareal spectral deferred corrections method. Commun. Appl. Math. Comput. Sci. 5, 265–301 (2010)
Minion, M.L., Speck, R., Bolten, M., Emmett, M., Ruprecht, D.: Interweaving PFASST and parallel multigrid. SIAM J. Sci. Comput. 37, S244–S263 (2015)
Nabben, R., Szyld, D.B.: Convergence theory of restricted multiplicative Schwarz methods. SIAM J. Numer. Anal. 40, 2318–2336 (2003)
Nevanlinna, O.: Linear acceleration of Picard–Lindelöf iteration. Numer. Math. 57, 147–156 (1990)
Nievergelt, J.: Parallel methods for integrating ordinary differential equations. Comm. ACM 7, 731–733 (1964)
Oosterlee, C.W., Wesseling, P.: Multigrid schemes for time-dependent incompressible Navier–Stokes equations. Impact Comput. Sci. Engry 5, 153–175 (1993)
Ruehli, A.E., Johnson, T.A.: Circuit analysis computing by waveform relaxation in encyclopedia of electrical and electronics engineering. Wiley, New York (1999)
Ruprecht, D., Speck, R., Krause, R.: Parareal for diffusion problems with space- and time-dependent coefficients. Domain decomposition methods in science and engineering XXII, 371–378, Lect. Notes Comput. Sci. Eng. 104, Springer, Cham (2016)
Simoens, J., Vandewalle, S.: Waveform relaxation with fast direct methods as preconditioner. SIAM J. Sci. Comput. 21, 1755–1773 (2000)
Smith, B., Bjørstad, P., Gropp, W.: Domain decomposition: parallel multilevel methods for elliptic partial differential equations. Cambridge University Press, Cambridge (1996)
Toselli, A., Widlund, O.B.: Domain decomposition methods—algorithms and theory. Springer, Berlin Heidelberg (2005)
Tran, M.-B.: Parallel Schwarz waveform relaxation algorithm for an N-dimensional semilinear heat equation. ESAIM Math. Model. Numer. Anal. 48, 795–813 (2014)
Trindade, J.M.F., Pereira, J.C.F.: Parallel-in-time simulation of two-dimensional, unsteady, incompressible laminar flows. Numer. Heat Trans. Part B Fund. 50, 25–40 (2006)
Vandewalle, S., Horton, G.: Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods. Computing 54, 317–330 (1995)
Vandewalle, S., Piessens, R.: Numerical experiments with nonlinear multigrid waveform relaxation on a parallel processor. Appl. Numer. Math. 8, 149–161 (1991)
Wu, S.-L., Xu, Y.: Convergence analysis of schwarz waveform relaxation with convolution transmission conditions. SIAM J. Sci. Comput. 39, A890–A921 (2017)
Wu, S.-L., Zhou, T.: Convergence analysis for three parareal solvers. SIAM J. Sci. Comput. 37, A970–A992 (2015)
Yang, H., Cai, X.-C.: Two-level space-time domain decomposition methods for flow control problems. J. Sci. Comput. 70, 717–743 (2017)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work was partly supported by the National Key R&D Program of China 2016YFB0200601, and the Shenzhen basic research grant JCYJ20160331193229720, JCYJ20170307165328836, JCYJ20170818153840322, and NSFC 11701133, 61531166003, 11726636.
Rights and permissions
About this article
Cite this article
Li, S., Shao, X. & Cai, XC. Highly parallel space-time domain decomposition methods for parabolic problems. CCF Trans. HPC 1, 25–34 (2019). https://doi.org/10.1007/s42514-019-00003-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s42514-019-00003-x
Keywords
- Parallel space-time method
- Additive Schwarz method
- Parabolic problem
- Implicit method
- Parallel scalability