×

A numerical framework for integrating deferred correction methods to solve high order collocation formulations of ODEs. (English) Zbl 1371.65072

Summary: Recent analysis and numerical experiments show that the deferred correction methods are competitive numerical schemes for time dependent differential equations. These methods differ in the mathematical formulations, choices of collocation points, and numerical integration or differentiation strategies. Existing analyses of these methods usually follow traditional theory of ordinary differential equations (ODEs) and study each algorithm’s convergence and stability properties as the step size \(\varDelta t\) varies. In this paper, we study the deferred correction methods from a different perspective by separating two different concepts in the algorithm: (1) the properties of the converged solution to the collocation formulation, and (2) the convergence procedure utilizing the deferred correction schemes to iteratively and efficiently reduce the error in the provisional solution. This new viewpoint allows the construction of a numerical framework to integrate existing techniques, by (1) selecting an appropriate collocation discretization based on the physical properties of the solution to balance the time step size and accuracy of the initial approximate solution; and by (2) applying different deferred correction strategies for reducing different components in the error of the provisional solution. This paper discusses properties of different components in the numerical framework, and presents preliminary results on the effective integration of these components for ODE initial value problems. Our results provide useful guidelines for implementing “optimal” time integration schemes for general time dependent differential equations.

MSC:

65L60 Finite element, Rayleigh-Ritz, Galerkin and collocation methods for ordinary differential equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
34A34 Nonlinear ordinary differential equations and systems
65L20 Stability and convergence of numerical methods for ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ascher, U., Petzold, L.: Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia (1998) · Zbl 0908.65055 · doi:10.1137/1.9781611971392
[2] Atkinson, K.: An Introduction to Numerical Analysis, 2nd edn. Wiley, Hoboken (1989) · Zbl 0718.65001
[3] Auzinger, W., Hofstatter, H., Kreuzer, W., Weinmuller, E.: Modified defect correction algorithms for ODEs. Part I: general theory. Numer. Algorithms 36, 135-156 (2004) · Zbl 1058.65068 · doi:10.1023/B:NUMA.0000033129.73715.7f
[4] Barrett, R., et al.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edn. SIAM, Philadelphia (1994) · doi:10.1137/1.9781611971538
[5] Barrio, R.: On the a-stability of Runge-Kutta collocation methods based on orthogonal polynomials. SIAM J. Numer. Anal. 36(4), 1291-1303 (1999) · Zbl 0942.65088 · doi:10.1137/S003614299732098X
[6] Beylkin, G., Sandberg, K.: Ode solvers using band-limited approximations. J. Comput. Phys. 265, 156-171 (2014) · Zbl 1349.65692 · doi:10.1016/j.jcp.2014.02.001
[7] Brown, P., Hindmarsh, A., Petzold, L.: Using Krylov methods in the solution of large-scale differential-algebraic systems. SIAM J. Sci. Comput. 15, 1467-1488 (1994) · Zbl 0812.65060 · doi:10.1137/0915088
[8] Canuto, C., Hussaini, M., Quarteroni, A., Zang, T.: Spectral Methods in Fluid Dynamics. Springer, Berlin (1988) · Zbl 0658.76001 · doi:10.1007/978-3-642-84108-8
[9] Causley, M., Christlieb, A., Ong, B., Van Groningen, L.: Method of lines transpose: an implicit solution to the wave equation. Math. Comput. 83, 2763-2786 (2014) · Zbl 1307.65122 · doi:10.1090/S0025-5718-2014-02834-2
[10] Chen, W., Wang, X., Yu, Y.: Reducing the computational requirements of the differential quadrature method. Numer. Methods Partial Differ. Equ. 12, 565-577 (1996) · Zbl 0868.65014 · doi:10.1002/(SICI)1098-2426(199609)12:5<565::AID-NUM2>3.0.CO;2-I
[11] Christlieb, A., Ong, B., Qiu, J.M.: Integral deferred correction methods constructed with high order Runge-Kutta integrators. Math. Comput. 79(270), 761-783 (2010) · Zbl 1209.65073 · doi:10.1090/S0025-5718-09-02276-5
[12] Dutt, A., Greengard, L., Rokhlin, V.: Spectral deferred correction methods for ordinary differential equations. BIT Numer. Math. 40(2), 241-266 (2000) · Zbl 0959.65084 · doi:10.1023/A:1022338906936
[13] Emmett, M., Minion, M.: Toward an efficient parallel in time method for partial differential equations. Commun. Appl. Math. Comput. Sci. 7(1), 105-132 (2012) · Zbl 1248.65106 · doi:10.2140/camcos.2012.7.105
[14] Gander, M.J., Vandewalle, S.: Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29(2), 556-578 (2007) · Zbl 1141.65064 · doi:10.1137/05064607X
[15] Glaser, A., Rokhlin, V.: A new class of highly accurate solvers for ordinary differential equations. J. Sci. Comput. 38(3), 368-399 (2009) · Zbl 1203.65102 · doi:10.1007/s10915-008-9245-1
[16] Gottlieb, D., Orszag, S.: Numerical Analysis of Spectral Methods. SIAM, Philadelphia (1977) · Zbl 0412.65058 · doi:10.1137/1.9781611970425
[17] Greengard, L.: Spectral integration and two-point boundary value problems. SIAM J. Numer. Anal. 28, 1071-1080 (1991) · Zbl 0731.65064 · doi:10.1137/0728057
[18] Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73, 325-348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9
[19] Hairer, E., Hairer, M.: Gnicodes—matlab programs for geometric numerical integration. In: Blowey, J., Craig, A., Shardlow, T. (eds.) Frontiers in Numerical Analysis, pp. 199-240. Springer, Berlin (2003) · Zbl 1028.65136
[20] Hairer, E., Lubich, C., Roche, M.: The Numerical Solution of Differential-Algebraic Systems by Runge-Kutta Methods. Springer, Berlin (1989) · Zbl 0683.65050
[21] Hairer, E., Lubich, C., Wanner, G.: Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer, Berlin (2002) · Zbl 0994.65135 · doi:10.1007/978-3-662-05018-7
[22] Hairer, E., Lubich, C., Wanner, G.: Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, vol. 31. Springer, Berlin (2006) · Zbl 1094.65125
[23] Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Springer, Berlin (1996) · Zbl 0859.65067 · doi:10.1007/978-3-642-05221-7
[24] Huang, J., Jia, J., Minion, M.: Accelerating the convergence of spectral deferred correction methods. J. Comput. Phys. 214, 633-656 (2006) · Zbl 1094.65066 · doi:10.1016/j.jcp.2005.10.004
[25] Huang, J., Jia, J., Minion, M.: Arbitrary order Krylov deferred correction methods for differential algebraic equations. J. Comput. Phys. 221(2), 739-760 (2007) · Zbl 1110.65076 · doi:10.1016/j.jcp.2006.06.040
[26] Jia, J., Huang, J.: Krylov deferred correction accelerated method of lines transpose for parabolic problems. J. Comput. Phys. 227(3), 1739-1753 (2008) · Zbl 1134.65064 · doi:10.1016/j.jcp.2007.09.018
[27] Jia, J., Liu, J.: Stable and spectrally accurate schemes for the Navier-Stokes equations. SIAM J. Sci. Comput. 33(5), 2421-2439 (2011) · Zbl 1232.65132 · doi:10.1137/090754340
[28] Kelly, C.: Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia (1995) · doi:10.1137/1.9781611970944
[29] Kelly, C.: Solving Nonlinear Equations with Newton’s Method. SIAM, Philadelphia (2003) · Zbl 1031.65069 · doi:10.1137/1.9780898718898
[30] Kennedy, C., Carpenter, M.H.: Additive Runge-Kutta schemes for convection-diffusion-reaction equations. Appl. Numer. Math. 44, 139-181 (2003) · Zbl 1013.65103 · doi:10.1016/S0168-9274(02)00138-1
[31] Knoll, D., Keyes, D.: Jacobian-free Newton-Krylov methods: a survey of approaches and applications. J. Comput. Phys. 193(2), 357-397 (2004) · Zbl 1036.65045 · doi:10.1016/j.jcp.2003.08.010
[32] Kushnir, D., Rokhlin, V.: A highly accurate solver for stiff ordinary differential equations. SIAM J. Sci. Comput. 34(3), A1296-A1315 (2012) · Zbl 1246.65103 · doi:10.1137/100810216
[33] 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(2), 341-373 (2005) · Zbl 1078.65552 · doi:10.1007/s10543-005-0016-1
[34] Li, S., Petzold, L.: Software and algorithms for sensitivity analysis of large-scale differential algebraic systems. J. Comput. Appl. Math. 125(1), 131-145 (2000) · Zbl 0971.65074 · doi:10.1016/S0377-0427(00)00464-7
[35] Lions, J., Maday, Y., Turinici, G.: A “parareal” in time discretization of PDE’s. Comptes Rendus de l’Academie des Sciences Series I Mathematics 332(7), 661-668 (2001) · Zbl 0984.65085
[36] Lu, B., Xiaolin, C., Huang, J., McCammon, A.: Order N algorithm for computation of electrostatic interactions in biomolecular systems. Proc. Nat. Acad. Sci. 103(51), 19314-19319 (2006) · doi:10.1073/pnas.0605166103
[37] Mazzia, F., et al.: Test set for IVP solvers. https://www.dm.uniba.it/ testset/testsetivpsolvers · Zbl 0731.65064
[38] Saad, Y., Schultz, M.: GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[39] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis. Springer, Berlin (1992) · Zbl 0771.65002
[40] Trefethen, L.: Is Gauss quadrature better than Clenshaw-Curtis? SIAM Rev. 50(1), 67-87 (2008) · Zbl 1141.65018 · doi:10.1137/060659831
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.