nach oben

BIT Numerical Mathematics

Erschienen in:

01.09.2015

A multi-level spectral deferred correction method

verfasst von: Robert Speck, Daniel Ruprecht, Matthew Emmett, Michael Minion, Matthias Bolten, Rolf Krause

Erschienen in: BIT Numerical Mathematics | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The spectral deferred correction (SDC) method is an iterative scheme for computing a higher-order collocation solution to an ODE by performing a series of correction sweeps using a low-order timestepping method. This paper examines a variation of SDC for the temporal integration of PDEs called multi-level spectral deferred corrections (MLSDC), where sweeps are performed on a hierarchy of levels and an FAS correction term, as in nonlinear multigrid methods, couples solutions on different levels. Three different strategies to reduce the computational cost of correction sweeps on the coarser levels are examined: reducing the degrees of freedom, reducing the order of the spatial discretization, and reducing the accuracy when solving linear systems arising in implicit temporal integration. Several numerical examples demonstrate the effect of multi-level coarsening on the convergence and cost of SDC integration. In particular, MLSDC can provide significant savings in compute time compared to SDC for a three-dimensional problem.

Vorheriger Artikel Convergence properties of a quadrature formula of Clenshaw–Curtis type for the Gegenbauer weight function

Nächster Artikel Backward perturbation analysis and residual-based error bounds for the linear response eigenvalue problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

We adopt here and in the upcoming examples the following notation: Solutions of PDEs are denoted with an underline, e.g. \(\underline{u}\), and depend continuously on one or more spatial variables and a time variable. Discretizing a PDE in space by the method of lines results in an IVP with dimension \(N\) equal to the degrees of freedom of the spatial discretization. The solution of such an IVP is a vector-valued function denoted by a lower case letter, e.g. \(u\), and depends continuously on time. The numerical approximation of \(u\) at some point in time \(t_{m}\) is denoted by a capital letter, e.g. \({U}_{m}^{k}\), where \(k\) corresponds to the iteration number.

Alam, J.M., Kevlahan, N.K.R., Vasilyev, O.V.: Simultaneous spacetime adaptive wavelet solution of nonlinear parabolic differential equations. J. Comput. Phys. 214(2), 829–857 (2006)MATHMathSciNetCrossRef

Ascher, U.M., Petzold, L.R.: Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia (2000)

Böhmer, K., Hemker, P., Stetter, H.J.: The defect correction approach. In: K. Böhmer, H.J. Stetter (eds.) Defect Correction Methods. Theory and Applications, pp. 1–32. Springer, Berlin (1984)

Bolten, M.: Evaluation of a multigrid solver for 3-level Toeplitz and circulant matrices on Blue Gene/Q. In: K. Binder, Münster, G., Kremer, M. (eds.) NIC Symposium 2014, pp. 345–352. John von Neumann Institute for Computing (2014, to appear)

Bourlioux, A., Layton, A.T., Minion, M.L.: High-order multi-implicit spectral deferred correction methods for problems of reactive flow. J. Comput. Phys. 189(2), 651–675 (2003)MATHMathSciNetCrossRef

Bouzarth, E.L., Minion, M.L.: A multirate time integrator for regularized stokeslets. J. Comput. Phys. 229(11), 4208–4224 (2010)MATHMathSciNetCrossRef

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

Briggs, W.L.: A Multigrid Tutorial. SIAM, Philadelphia (1987)MATH

Chorin, A.J., Marsden, J.E.: A Mathematical Introduction to Fluid Mechanics, 2nd edn. Springer, Berlin (1990)

10.

Chow, E., Falgout, R.D., Hu, J.J., Tuminaro, R.S., Yang, U.M.: A survey of parallelization techniques for multigrid solvers. In: Parallel Processing for Scientific Computing, SIAM Series of Software, Environements and Tools. SIAM (2006)

11.

Christlieb, A., Morton, M., Ong, B., Qiu, J.M.: Semi-implicit integral deferred correction constructed with additive Runge–Kutta methods. Commun. Math. Sci. 9(3), 879–902 (2011)MATHMathSciNetCrossRef

12.

Christlieb, A., Ong, B., Qiu, J.M.: Comments on high-order integrators embedded within integral deferred correction methods. Commun. Appl. Math. Comput. Sci. 4(1), 27–56 (2009)MATHMathSciNetCrossRef

13.

Christlieb, A., Ong, B.W., Qiu, J.M.: Integral deferred correction methods constructed with high order Runge-Kutta integrators. Math. Comput. 79, 761–783 (2010)MATHMathSciNetCrossRef

14.

Dai, X., Le Bris, C., Legoll, F., Maday, Y.: Symmetric parareal algorithms for Hamiltonian systems. ESAIM. Math. Model. Numer. Anal. 47, 717–742 (2013)MATHMathSciNetCrossRef

15.

Daniel, J.W., Pereyra, V., Schumaker, L.L.: Iterated deferred corrections for initial value problems. Acta Cient. Venezolana 19, 128–135 (1968)MathSciNet

16.

Dutt, A., Greengard, L., Rokhlin, V.: Spectral deferred correction methods for ordinary differential equations. BIT Numer. Math. 40(2), 241–266 (2000)MATHMathSciNetCrossRef

17.

Emmett, M., Minion, M.L.: Efficient implementation of a multi-level parallel in time algorithm. In: Proceedings of the 21st International Conference on Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering. Springer (2012)

18.

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

19.

Hagstrom, T., Zhou, R.: On the spectral deferred correction of splitting methods for initial value problems. Commun. Appl. Math. Comput. Sci. 1(1), 169–205 (2006)MATHMathSciNetCrossRef

20.

Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I, Nonstiff Problems. Springer, Berlin (1987)

21.

Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems. Springer, Berlin (1991)MATHCrossRef

22.

Hansen, A.C., Strain, J.: Convergence theory for spectral deferred correction (2006, preprint)

23.

Haut, T., Wingate, B.: An asymptotic parallel-in-time method for highly oscillatory PDEs. SIAM J. Sci. Comput. (2014, in press)

24.

Huang, J., Jia, J., Minion, M.: Accelerating the convergence of spectral deferred correction methods. J. Comput. Phys. 214(2), 633–656 (2006)MATHMathSciNetCrossRef

25.

Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)CrossRef

26.

Jiang, G.S., Shu, C.W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202–228 (1996)MATHMathSciNetCrossRef

27.

Layton, A.T.: On the efficiency of spectral deferred correction methods for time-dependent partial differential equations. Appl. Numer. Math. 59(7), 1629–1643 (2009)MATHMathSciNetCrossRef

28.

Layton, A.T., Minion, M.L.: Conservative multi-implicit spectral deferred correction methods for reacting gas dynamics. J. Comput. Phys. 194(2), 697–715 (2004)MATHMathSciNetCrossRef

29.

Layton, A.T., Minion, M.L.: Implications of the choice of quadrature nodes for Picard integral deferred corrections methods for ordinary differential equations. BIT Numer. Math. 45, 341–373 (2005)MATHMathSciNetCrossRef

30.

Lele, S.K.: Compact finite difference schemes with spectral-like resolution. J. Comput. Phys. 103(1), 16–42 (1992)MATHMathSciNetCrossRef

31.

Minion, M.L.: Semi-implicit spectral deferred correction methods for ordinary differential equations. Commun. Math. Sci. 1(3), 471–500 (2003)MATHMathSciNetCrossRef

32.

Minion, M.L.: Semi-implicit projection methods for incompressible flow based on spectral deferred corrections. Appl. Numer. Math. 48(3), 369–387 (2004)MATHMathSciNetCrossRef

33.

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

34.

Pereyra, V.: Iterated deferred corrections for nonlinear operator equations. Numer. Math. 10, 316–323 (1966)MathSciNetCrossRef

35.

Pereyra, V.: On improving an approximate solution of a functional equation by deferred corrections. Numer. Math. 8, 376–391 (1966)MATHMathSciNetCrossRef

36.

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

37.

South, J.C., Brandt, A.: Application of a multi-level grid method to transonic flow calculations. In: Transonic Flow Problems in Turbomachinery, Hemisphere, pp. 180–206 (1977)

38.

Speck, R., Ruprecht, D., Krause, R., Emmett, M., Minion, M., Winkel, M., Gibbon, P.: A massively space-time parallel N-body solver. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC ’12, pp. 92:1–92:11. IEEE Computer Society Press, Los Alamitos (2012)

39.

Speck, R., Ruprecht, D., Minion, M., Emmett, M., Krause, R.: Inexact spectral deferred corrections In: Domain Decomposition Methods in Science and Engineering XXII, Lecture Notes in Computational Science and Engineering (2014, accepted). arXiv:1401.7824

40.

Spotz, W.F., Carey, G.F.: A high-order compact formulation for the 3D Poisson equation. Numer. Methods Partial Differ. Equ. 12(2), 235–243 (1996)MATHMathSciNetCrossRef

41.

Stetter, H.J.: Economical global error estimation. In: Willoughby, R.A. (ed.) Stiff Differential Systems, pp. 245–258 (1974)

42.

Trottenberg, U., Oosterlee, C.W.: Multigrid: Basics. Parallelism and Adaptivity. Academic Press, London (2000)

43.

Weiser, M.: Faster SDC convergence on non-equidistant grids with DIRK sweeps (2013). ZIB Report, pp 13–30

44.

Xia, Y., Xu, Y., Shu, C.W.: Efficient time discretization for local discontinuous Galerkin methods. Discrete Contin. Dyn. Syst. Ser. B 8(3), 677–693 (2007)MATHMathSciNetCrossRef

45.

Zadunaisky, P.: A method for the estimation of errors propagated in the numerical solution of a system of ordinary differential equations. In: Contopoulus, G. (ed.) The Theory of Orbits in the Solar System and in Stellar Systems. Proceedings of International Astronomical Union, Symposium 25 (1964)

Titel: A multi-level spectral deferred correction method
verfasst von: Robert Speck
Daniel Ruprecht
Matthew Emmett
Michael Minion
Matthias Bolten
Rolf Krause
Publikationsdatum: 01.09.2015
Verlag: Springer Netherlands
Erschienen in: BIT Numerical Mathematics / Ausgabe 3/2015
Print ISSN: 0006-3835
Elektronische ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-014-0517-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2015

Spline element method for Monge–Ampère equations

Superconvergent cubic spline quasi-interpolants on Powell-Sabin partitions

Convergence properties of a quadrature formula of Clenshaw–Curtis type for the Gegenbauer weight function

Backward perturbation analysis and residual-based error bounds for the linear response eigenvalue problem

Monotone iterative ADI method for semilinear parabolic problems

Axel Ruhe 1942–2015