Applications of Mathematics, Vol. 63, No. 3, pp. 219-235, 2018


Computing discrete convolutions with verified accuracy via Banach algebras and the FFT

Jean-Philippe Lessard

Received March 26, 2018.   Published online May 23, 2018.

Abstract:  We introduce a method to compute rigorous component-wise enclosures of discrete convolutions using the fast Fourier transform, the properties of Banach algebras, and interval arithmetic. The purpose of this new approach is to improve the implementation and the applicability of computer-assisted proofs performed in weighed $\ell^1$ Banach algebras of Fourier/Chebyshev sequences, whose norms are known to be numerically unstable. We introduce some application examples, in particular a rigorous aposteriori error analysis for a steady state in the quintic Swift-Hohenberg PDE.
Keywords:  discrete convolutions; Banach algebras; fast Fourier transform; interval arithmetic; rigorously verified numerics; quintic Swift-Hohenberg PDE
Classification MSC:  65G40, 65T50, 46J15, 46B45, 42B05


References:
[1] J. P. Boyd: Chebyshev and Fourier Spectral Methods. Dover Publications, Mineola (2001). MR 1874071 | Zbl 0994.65128
[2] E. Brigham: Fast Fourier Transform and Its Applications. Prentice Hall, Upper Saddle River (1988).
[3] J. Cyranka: Efficient and generic algorithm for rigorous integration forward in time of dPDEs. I. J. Sci. Comput. 59 (2014), 28-52. DOI 10.1007/s10915-013-9749-1 | MR 3167726 | Zbl 1296.65138
[4] S. Day, Y. Hiraoka, K. Mischaikow, T. Ogawa: Rigorous numerics for global dynamics: a study of the Swift-Hohenberg equation. SIAM J. Appl. Dyn. Syst. 4 (2005), 1-31. DOI 10.1137/040604479 | MR 2136516 | Zbl 1058.35050
[5] S. Day, O. Junge, K. Mischaikow: A rigorous numerical method for the global analysis of infinite-dimensional discrete dynamical systems. SIAM J. Appl. Dyn. Syst. 3 (2004), 117-160. DOI 10.1137/030600210 | MR 2067140 | Zbl 1059.37068
[6] S. Day, W. D. Kalies: Rigorous computation of the global dynamics of integrodifference equations with smooth nonlinearities. SIAM J. Numer. Anal. 51 (2013), 2957-2983. DOI 10.1137/120903129 | MR 3124898 | Zbl 1288.37030
[7] S. Day, J.-P. Lessard, K. Mischaikow: Validated continuation for equilibria of PDEs. SIAM J. Numer. Anal. 45 (2007), 1398-1424. DOI 10.1137/050645968 | MR 2338393 | Zbl 1151.65074
[8] J.-L. Figueras, R. de la Llave: Numerical computations and computer assisted proofs of periodic orbits of the Kuramoto-Sivashinsky equation. SIAM J. Appl. Dyn. Syst. 16 (2017), 834-852. DOI 10.1137/16M1073790 | MR 3633778 | Zbl 1370.65047
[9] J.-L. Figueras, A. Haro, A. Luque: Rigorous computer-assisted application of KAM theory: a modern approach. Found. Comput. Math. 17 (2017), 1123-1193. DOI 10.1007/s10208-016-9339-3 | MR 3709329 | Zbl 06814851
[10] M. Gameiro, J.-P. Lessard: Analytic estimates and rigorous continuation for equilibria of higher-dimensional PDEs. J. Differ. Equations 249 (2010), 2237-2268. DOI 10.1016/j.jde.2010.07.002 | MR 2718657 | Zbl 1256.35196
[11] M. Gameiro, J.-P. Lessard, K. Mischaikow: Validated continuation over large parameter ranges for equilibria of PDEs. Math. Comput. Simul. 79 (2008), 1368-1382. DOI 10.1016/j.matcom.2008.03.014 | MR 2487806 | Zbl 1166.65379
[12] M. Gameiro, J.-P. Lessard, Y. Ricaud: Rigorous numerics for piecewise-smooth systems: a functional analytic approach based on Chebyshev series. J. Comput. Appl. Math. 292 (2016), 654-673. DOI 10.1016/j.cam.2015.05.016 | MR 3392421 | Zbl 1323.65123
[13] Y. Hiraoka, T. Ogawa: Rigorous numerics for localized patterns to the quintic Swift-Hohenberg equation. Japan J. Ind. Appl. Math. 22 (2005), 57-75. DOI 10.1007/BF03167476 | MR 2126387 | Zbl 1067.65146
[14] Y. Hiraoka, T. Ogawa: An efficient estimate based on FFT in topological verification method. J. Comput. Appl. Math. 199 (2007), 238-244. DOI 10.1016/j.cam.2005.08.036 | MR 2269503 | Zbl 1109.65110
[15] A. Hungria, J.-P. Lessard, J. D. Mireles James: Rigorous numerics for analytic solutions of differential equations: the radii polynomial approach. Math. Comput. 85 (2016), 1427-1459. DOI 10.1090/mcom/3046 | MR 3454370 | Zbl 1332.65114
[16] H. Koch, A. Schenkel, P. Wittwer: Computer-assisted proofs in analysis and programming in logic: A case study. SIAM Rev. 38 (1996), 565-604. DOI 10.1137/S0036144595284180 | MR 1420838 | Zbl 0865.68111
[17] J.-P. Lessard, J. D. Mireles James, J. Ransford: Automatic differentiation for Fourier series and the radii polynomial approach. Physica D 334 (2016), 174-186. DOI 10.1016/j.physd.2016.02.007 | MR 3545977
[18] J.-P. Lessard, C. Reinhardt: Rigorous numerics for nonlinear differential equations using Chebyshev series. SIAM J. Numer. Anal. 52 (2014), 1-22. DOI 10.1137/13090883X | MR 3148084 | Zbl 1290.65060
[19] J. D. Mireles James, K. Mischaikow: Computational proofs in dynamics. Encyclopedia of Applied and Computational Mathematics (B. Engquist, ed.). Springer, Berlin (2015). DOI 10.1007/978-3-540-70529-1_322
[20] R. E. Moore: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966). MR 0231516 | Zbl 0176.13301
[21] M. T. Nakao: Numerical verification methods for solutions of ordinary and partial differential equations. Numer. Funct. Anal. Optimization 22 (2001), 321-356. DOI 10.1081/NFA-100105107 | MR 1849323 | Zbl 1106.65315
[22] S. M. Rump: INTLAB - INTerval LABoratory. Developments in Reliable Computing (T. Csendes, ed.). Kluwer Academic Publishers, Dordrecht, 1999, pp. 77-104. Available at http://www.ti3.tu-harburg.de/rump/intlab/. Zbl 0949.65046
[23] S. M. Rump: Verification methods: rigorous results using floating-point arithmetic. Acta Numerica 19 (2010), 287-449. DOI 10.1017/S096249291000005X | MR 2652784 | Zbl 1323.65046
[24] H. Sakaguchi, H. R. Brand: Stable localized solutions of arbitrary length for the quintic Swift-Hohenberg equation. Physica D 97 (1996), 274-285. DOI 10.1016/0167-2789(96)00077-2
[25] W. Tucker: Validated Numerics. A Short Introduction to Rigorous Computations. Princeton University Press, Princeton (2011). MR 2807595 | Zbl 1231.65077
[26] J. B. van den Berg, C. M. Groothedde, J.-P. Lessard: A general method for computer-assisted proofs of periodic solutions in delay differential problems. Preprint (2018).
[27] J. B. van den Berg, J.-P. Lessard: Rigorous numerics in dynamics. Notices Am. Math. Soc. 62 (2015), 1057-1061. DOI 10.1090/noti1276 | MR 3444942 | Zbl 1338.68301
[28] J. B. van den Berg, J. F. Williams: Validation of the bifurcation diagram in the 2D Ohta-Kawasaki problem. Nonlinearity 30 (2017), 1584-1638. DOI 10.1088/1361-6544/aa60e8 | MR 3636312 | Zbl 1366.65068
[29] C. F. Van Loan: Computational Frameworks for the Fast Fourier Transform. Frontiers in Applied Mathematics 10, SIAM, Philadelphia (1992). DOI 10.1137/1.9781611970999 | MR 1153025 | Zbl 0757.65154
[30] D. Wilczak, P. Zgliczynski: Heteroclinic connections between periodic orbits in planar restricted circular three-body problem - a computer-assisted proof. Commun. Math. Phys. 234 (2003), 37-75. DOI 10.1007/s00220-002-0709-0 | MR 1961956 | Zbl 1055.70005
[31] P. Zgliczyński: Rigorous numerics for dissipative PDEs. III: An effective algorithm for rigorous integration of dissipative PDEs. Topol. Methods Nonlinear Anal. 36 (2010), 197-262. MR 2788972 | Zbl 1230.65113
[32] P. Zgliczyński, K. Mischaikow: Rigorous numerics for partial differential equations: The Kuramoto-Sivashinsky equation. Found. Comput. Math. 1 (2001), 255-288. DOI 10.1007/s102080010010 | MR 1838755 | Zbl 0984.65101

Affiliations:   Jean-Philippe Lessard, McGill University, Department of Mathematics and Statistics, 805 Sherbrooke Street West, Montreal, QC, H3A 0B9, Canada, e-mail: jp.lessard@mcgill.ca


 
PDF available at: