iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s42514-019-00003-x
Highly parallel space-time domain decomposition methods for parabolic problems | CCF Transactions on High Performance Computing Skip to main content
Log in

Highly parallel space-time domain decomposition methods for parabolic problems

  • Regular Paper
  • Published:
CCF Transactions on High Performance Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3

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)

    Article  MathSciNet  MATH  Google Scholar 

  • Badia, S., Olmand, M.: Space-time balancing domain decomposition. SIAM J. Sci. Comput. 39, C194–C213 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  Google Scholar 

  • Bjorhus, M., Stuart, A.M.: Waveform relaxation as a dynamical system. Math. Comp. 66, 1101–1117 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Burrage, K.: Parallel and sequential methods for ordinary differential equations. Oxford Science Publications, New York (1995)

    MATH  Google Scholar 

  • Cai, X.-C., Sarkis, M.: A restricted additive Schwarz preconditioner for general sparse linear systems. SIAM J. Sci. Comput. 21, 792–797 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Gander, M.J.: A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations. Numer. Linear Algebra Appl. 6, 125–145 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  • Gander, M.J.: Optimized schwarz methods. SIAM J. Numer. Anal. 44, 699–731 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Giladi, E., Keller, H.B.: Space-time domain decomposition for parabolic problems. Numer. Math. 93, 279–313 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Jeltsch, R., Pohl, B.: Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput. 16, 40–49 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Li, S., Shao, X., Cai, X.-C.: Multilevel space-time additive Schwarz methods for parabolic equations. SIAM J. Sci. Comput. 40, A3012–A3037 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Maday, Y., Salomon, J., Turinici, G.: Monotonic parareal control for quantum systems. SIAM J. Numer. Anal. 45, 2468–2482 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Miekkala, U., Nevanlinna, O.: Convergence of dynamic iteration methods for initial value problem. SIAM J. Sci. Stat. Comput. 8, 459–482 (1987)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Nabben, R., Szyld, D.B.: Convergence theory of restricted multiplicative Schwarz methods. SIAM J. Numer. Anal. 40, 2318–2336 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Nevanlinna, O.: Linear acceleration of Picard–Lindelöf iteration. Numer. Math. 57, 147–156 (1990)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Oosterlee, C.W., Wesseling, P.: Multigrid schemes for time-dependent incompressible Navier–Stokes equations. Impact Comput. Sci. Engry 5, 153–175 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  • Ruehli, A.E., Johnson, T.A.: Circuit analysis computing by waveform relaxation in encyclopedia of electrical and electronics engineering. Wiley, New York (1999)

    Google Scholar 

  • 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)

    Article  MathSciNet  MATH  Google Scholar 

  • Smith, B., Bjørstad, P., Gropp, W.: Domain decomposition: parallel multilevel methods for elliptic partial differential equations. Cambridge University Press, Cambridge (1996)

    MATH  Google Scholar 

  • Toselli, A., Widlund, O.B.: Domain decomposition methods—algorithms and theory. Springer, Berlin Heidelberg (2005)

    Book  MATH  Google Scholar 

  • Tran, M.-B.: Parallel Schwarz waveform relaxation algorithm for an N-dimensional semilinear heat equation. ESAIM Math. Model. Numer. Anal. 48, 795–813 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  • 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)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Vandewalle, S., Piessens, R.: Numerical experiments with nonlinear multigrid waveform relaxation on a parallel processor. Appl. Numer. Math. 8, 149–161 (1991)

    Article  MATH  Google Scholar 

  • Wu, S.-L., Xu, Y.: Convergence analysis of schwarz waveform relaxation with convolution transmission conditions. SIAM J. Sci. Comput. 39, A890–A921 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  • Wu, S.-L., Zhou, T.: Convergence analysis for three parareal solvers. SIAM J. Sci. Comput. 37, A970–A992 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Yang, H., Cai, X.-C.: Two-level space-time domain decomposition methods for flow control problems. J. Sci. Comput. 70, 717–743 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Xiao-Chuan Cai.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s42514-019-00003-x

Keywords

Mathematics Subject Classification

Navigation