×

Efficient and generic algorithm for rigorous integration forward in time of dPDEs. I. (English) Zbl 1296.65138

Summary: We propose an efficient and generic algorithm for rigorous integration forward in time of partial differential equations written in the Fourier basis. By rigorous integration we mean a procedure which operates on sets and return sets which are guaranteed to contain the exact solution. The presented algorithm generates, in an efficient way, normalized derivatives which are used by the Lohner algorithm to produce a rigorous bound. The algorithm has been successfully tested on several partial differential equations (PDEs) including the Burgers equation, the Kuramoto-Sivashinsky equation, and the Swift-Hohenberg equation. The problem of rigorous integration in time of partial differential equations is a problem of large computational complexity and efficient algorithms are required to deal with PDEs on higher dimensional domains, like the Navier-Stokes equation. Technicalities regarding the various optimization techniques implemented in the software used in this paper will be reported elsewhere.

MSC:

65M99 Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems
35B40 Asymptotic behavior of solutions to PDEs
35B41 Attractors
65G20 Algorithms with automatic result verification
65M70 Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs
65Y20 Complexity and performance of numerical algorithms
65T50 Numerical methods for discrete and fast Fourier transforms

Software:

Taylor; CAPD; FADBAD++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arioli, G., Koch, H.: Integration of dissipative partial differential equations: a case study. SIAM J. Appl. Dyn. Syst. 9, 1119-1133 (2010) · Zbl 1298.37071 · doi:10.1137/10078298X
[2] Bendtsen, C., Stauning, O.: FADBAD, a Flexible C++ Package for Automatic Differentiation. Technical University of Denmark, Department of Mathematical Modelling, Copenhagen (1996)
[3] Breuer, B., McKenna, P.J., Plum, M.: Multiple solutions for a semilinear boundary value problem: a computational multiplicity proof. J. Differ. Equ. 195, 243-269 (2003) · Zbl 1156.35359 · doi:10.1016/S0022-0396(03)00186-4
[4] CAPD—computer assisted proofs in dynamics, a package for rigorous numeric, http://capd.ii.uj.edu.pl · Zbl 0513.65092
[5] Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.: Spectral Methods. Fundamentals in Single Domains. Springer, Berlin (2006) · Zbl 1093.76002
[6] Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comp. 19, 297-301 (1965) · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[7] Cyranka, J.: Existence of Globally Attracting Fixed Points of Viscous Burgers Equation with Constant Forcing. A Computer Assisted Proof, preprint, 2011, available on-line http://www.ii.uj.edu.pl/ cyranka · Zbl 1365.65220
[8] Cyranka, J.: Efficient Algorithms for Rigorous Integration Forward in Time of dPDEs. Existence of Globally Attracting Fixed Points of Viscous Burgers Equation with Constant Forcing, a Computer Assisted Proof, PhD dissertation, Jagiellonian University, Cracow, 2013, available on-line http://www.ii.uj.edu.pl/ cyranka · Zbl 1106.65315
[9] Day, S., Hiraoka, Y., Mischaikow, K., Ogawa, T.: Rigorous numerics for global dynamics: a study of Swift-Hohenberg equation. SIAM J. Appl. Dyn. Syst. 4, 1-31 (2005) · Zbl 1058.35050 · doi:10.1137/040604479
[10] Day, S., Lessard, J.P., Mischaikow, K.: Validated continuation for equilibria of PDEs. SIAM J. Numer. Anal. 45, 1398-1424 (2007) · Zbl 1151.65074 · doi:10.1137/050645968
[11] Gameiro, M., Lessard, J.P., Mischaikow, K.: Validated continuation over large parameter ranges for equilibria of PDEs. Math. Comput. Simul. 79, 1368-1382 (2008) · Zbl 1166.65379 · doi:10.1016/j.matcom.2008.03.014
[12] Gameiro, M., Lessard, J.P.: Analytic estimates and rigorous continuation for equilibria of higher-dimensional PDEs. J. Differ. Equ. 249, 2237-2268 (2010) · Zbl 1256.35196 · doi:10.1016/j.jde.2010.07.002
[13] Gameiro, M., Lessard, J.P.: Rigorous computation of smooth branches of equilibria for the three dimensional Cahn-Hilliard equation. Numer. Math. 117, 753-778 (2011) · Zbl 1216.65145 · doi:10.1007/s00211-010-0350-3
[14] Griewank, A.: Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation, Frontiers in Applied Mathematics, vol. 19. SIAM, Philadelphia (2000) · Zbl 0958.65028
[15] Heywood, J.G., Nagata, W., Xie, W.: A numerically based existence theorem for the Navier-Stokes equations. J. Math. Fluid. Mech. 1, 5-23 (1999) · Zbl 0934.35115 · doi:10.1007/s000210050002
[16] Hiraoka, Y., Ogawa, T.: Rigorous numerics for localized patterns to the quintic Swift-Hohenberg equation, Japan. J. Ind. Appl. Math. 22, 57-75 (2005) · Zbl 1067.65146 · doi:10.1007/BF03167476
[17] Hiraoka, Y., Ogawa, T.: An efficient estimate based on FFT in topological verification method. J. Comput. Appl. Math. 199, 238-244 (2007) · Zbl 1109.65110 · doi:10.1016/j.cam.2005.08.036
[18] Jorba, Á., Zou, M.: A software package for the numerical integration of ODEs by means of high-order Taylor methods. Exp. Math. 14, 99-117 (2005) · Zbl 1108.65072 · doi:10.1080/10586458.2005.10128904
[19] Kapela, T., Zgliczyński, P.: A Lohner-type algorithm for control systems and ordinary differential inclusions. Discret. Cont. Dyn. Sys. B 11, 365-385 (2009) · Zbl 1185.65079 · doi:10.3934/dcdsb.2009.11.365
[20] Kim, M., Nakao, M.T., Watanabe, Y., Nishida, T.: A numerical verification method of bifurcating solutions for 3-dimensional Rayleigh-Bénard problems. Numer. Math. 111, 389-406 (2009) · Zbl 1155.76024 · doi:10.1007/s00211-008-0191-5
[21] Lohner, RJ; Cash, JR (ed.); Gladwell, I. (ed.), Computation of guaranteed enclosures for the solutions of ordinary initial and boundary value problems (1992), Oxford · Zbl 0767.65069
[22] Maier-Paape, S., Miller, U., Mischaikow, K., Wanner, T.: Rigorous numerics for the Cahn-Hilliard equation on the unit square. Rev. Mat. Complut. 21, 351-426 (2008) · Zbl 1160.37418
[23] Moore, R.E.: Interval Analysis. Prentice-Hall, New Jersey (1966) · Zbl 0176.13301
[24] Moore, R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979) · Zbl 0417.65022 · doi:10.1137/1.9781611970906
[25] Nakao, M.T.: Numerical verification methods for solutions of ordinary and partial differential equations. Numer. Funct. Anal. Optim. 22, 321-356 (2001) · Zbl 1106.65315 · doi:10.1081/NFA-100105107
[26] Orszag, S.A., Patterson, G.S.: Spectral calculations of isotropic turbulence: efficient removal of aliasing interactions. Phys. Fluids 14, 2538-2541 (1971) · Zbl 0225.76033 · doi:10.1063/1.1693365
[27] Simó, C.: Taylor Method for the Integration of ODE. Lectures given at the LTI07 Advanced School on Long Time Integrations, available online http://www.maia.ub.es/dsg/2007/ · Zbl 0513.65094
[28] Software package and the data from tests, http://www.ii.uj.edu.pl/ cyranka/FFT
[29] Temperton, C.: Self-sorting mixed-radix fast fourier transforms. J. Comput. Phys. 52, 1-23 (1983) · Zbl 0513.65092 · doi:10.1016/0021-9991(83)90013-X
[30] Temperton, C.: Fast mixed-radix real fourier transforms. J. Comput. Phys. 52, 340-350 (1983) · Zbl 0513.65094 · doi:10.1016/0021-9991(83)90034-7
[31] Warmus, M.: Calculus of Approximations. Bull. de l’Académie Polonaise des Sciences Cl. III 4, 253-259 (1956) · Zbl 0071.12503
[32] Zgliczyński, P.: Attracting fixed points for the Kuramoto-Sivashinsky equation—a computer assisted proof. SIAM J. Appl. Dyn. Syst. 1, 215-288 (2002) · Zbl 1004.35017 · doi:10.1137/S111111110240176X
[33] Zgliczyński, \[P.: C^1\] C1-Lohner algorithm. Found. Comput. Math. 2, 429-465 (2002) · Zbl 1049.65038 · doi:10.1007/s102080010025
[34] Zgliczyński, P.: Rigorous numerics for dissipative partial differential equations II. Periodic orbit for the Kuramoto-Sivashinsky PDE—a computer assisted proof. Found. Comput. Math. 4, 157-185 (2004) · Zbl 1066.65105 · doi:10.1007/s10208-002-0080-8
[35] Zgliczyński, P.: Rigorous numerics for dissipative PDEs III. An effective algorithm for rigorous integration of dissipative PDEs. Topol. Methods Nonlinear Anal. 36, 197-262 (2010) · Zbl 1230.65113
[36] Zgliczyński, P., Mischaikow, K.: Rigorous numerics for partial differential equations: the Kuramoto-Sivashinsky equation. Found. Comput. Math. 1, 255-288 (2001) · Zbl 0984.65101 · doi:10.1007/s002080010010
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.