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

Jean-Philippe Lessard

Applications of Mathematics (2018)

  • Volume: 63, Issue: 3, page 219-235
  • ISSN: 0862-7940

Abstract

top
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 ℓ 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.

How to cite

top

Lessard, Jean-Philippe. "Computing discrete convolutions with verified accuracy via Banach algebras and the FFT." Applications of Mathematics 63.3 (2018): 219-235. <http://eudml.org/doc/294804>.

@article{Lessard2018,
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.},
author = {Lessard, Jean-Philippe},
journal = {Applications of Mathematics},
keywords = {discrete convolutions; Banach algebras; fast Fourier transform; interval arithmetic; rigorously verified numerics; quintic Swift-Hohenberg PDE},
language = {eng},
number = {3},
pages = {219-235},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Computing discrete convolutions with verified accuracy via Banach algebras and the FFT},
url = {http://eudml.org/doc/294804},
volume = {63},
year = {2018},
}

TY - JOUR
AU - Lessard, Jean-Philippe
TI - Computing discrete convolutions with verified accuracy via Banach algebras and the FFT
JO - Applications of Mathematics
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 3
SP - 219
EP - 235
AB - 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.
LA - eng
KW - discrete convolutions; Banach algebras; fast Fourier transform; interval arithmetic; rigorously verified numerics; quintic Swift-Hohenberg PDE
UR - http://eudml.org/doc/294804
ER -

References

top
  1. Boyd, J. P., Chebyshev and Fourier Spectral Methods, Dover Publications, Mineola (2001). (2001) Zbl0994.65128MR1874071
  2. Brigham, E., Fast Fourier Transform and Its Applications, Prentice Hall, Upper Saddle River (1988). (1988) 
  3. Cyranka, J., 10.1007/s10915-013-9749-1, J. Sci. Comput. 59 (2014), 28-52. (2014) Zbl1296.65138MR3167726DOI10.1007/s10915-013-9749-1
  4. Day, S., Hiraoka, Y., Mischaikow, K., Ogawa, T., 10.1137/040604479, SIAM J. Appl. Dyn. Syst. 4 (2005), 1-31. (2005) Zbl1058.35050MR2136516DOI10.1137/040604479
  5. Day, S., Junge, O., Mischaikow, K., 10.1137/030600210, SIAM J. Appl. Dyn. Syst. 3 (2004), 117-160. (2004) Zbl1059.37068MR2067140DOI10.1137/030600210
  6. Day, S., Kalies, W. D., 10.1137/120903129, SIAM J. Numer. Anal. 51 (2013), 2957-2983. (2013) Zbl1288.37030MR3124898DOI10.1137/120903129
  7. Day, S., Lessard, J.-P., Mischaikow, K., 10.1137/050645968, SIAM J. Numer. Anal. 45 (2007), 1398-1424. (2007) Zbl1151.65074MR2338393DOI10.1137/050645968
  8. Figueras, J.-L., Llave, R. de la, 10.1137/16M1073790, SIAM J. Appl. Dyn. Syst. 16 (2017), 834-852. (2017) Zbl1370.65047MR3633778DOI10.1137/16M1073790
  9. Figueras, J.-L., Haro, A., Luque, A., 10.1007/s10208-016-9339-3, Found. Comput. Math. 17 (2017), 1123-1193. (2017) Zbl06814851MR3709329DOI10.1007/s10208-016-9339-3
  10. Gameiro, M., Lessard, J.-P., 10.1016/j.jde.2010.07.002, J. Differ. Equations 249 (2010), 2237-2268. (2010) Zbl1256.35196MR2718657DOI10.1016/j.jde.2010.07.002
  11. Gameiro, M., Lessard, J.-P., Mischaikow, K., 10.1016/j.matcom.2008.03.014, Math. Comput. Simul. 79 (2008), 1368-1382. (2008) Zbl1166.65379MR2487806DOI10.1016/j.matcom.2008.03.014
  12. Gameiro, M., Lessard, J.-P., Ricaud, Y., 10.1016/j.cam.2015.05.016, J. Comput. Appl. Math. 292 (2016), 654-673. (2016) Zbl1323.65123MR3392421DOI10.1016/j.cam.2015.05.016
  13. Hiraoka, Y., Ogawa, T., 10.1007/BF03167476, Japan J. Ind. Appl. Math. 22 (2005), 57-75. (2005) Zbl1067.65146MR2126387DOI10.1007/BF03167476
  14. Hiraoka, Y., Ogawa, T., 10.1016/j.cam.2005.08.036, J. Comput. Appl. Math. 199 (2007), 238-244. (2007) Zbl1109.65110MR2269503DOI10.1016/j.cam.2005.08.036
  15. Hungria, A., Lessard, J.-P., James, J. D. Mireles, 10.1090/mcom/3046, Math. Comput. 85 (2016), 1427-1459. (2016) Zbl1332.65114MR3454370DOI10.1090/mcom/3046
  16. Koch, H., Schenkel, A., Wittwer, P., 10.1137/S0036144595284180, SIAM Rev. 38 (1996), 565-604. (1996) Zbl0865.68111MR1420838DOI10.1137/S0036144595284180
  17. Lessard, J.-P., James, J. D. Mireles, Ransford, J., 10.1016/j.physd.2016.02.007, Physica D 334 (2016), 174-186. (2016) MR3545977DOI10.1016/j.physd.2016.02.007
  18. Lessard, J.-P., Reinhardt, C., 10.1137/13090883X, SIAM J. Numer. Anal. 52 (2014), 1-22. (2014) Zbl1290.65060MR3148084DOI10.1137/13090883X
  19. James, J. D. Mireles, Mischaikow, K., 10.1007/978-3-540-70529-1_322, Encyclopedia of Applied and Computational Mathematics B. Engquist Springer, Berlin (2015). (2015) MR3470172DOI10.1007/978-3-540-70529-1_322
  20. Moore, R. E., Interval Analysis, Prentice-Hall, Englewood Cliffs (1966). (1966) Zbl0176.13301MR0231516
  21. Nakao, M. T., 10.1081/NFA-100105107, Numer. Funct. Anal. Optimization 22 (2001), 321-356. (2001) Zbl1106.65315MR1849323DOI10.1081/NFA-100105107
  22. Rump, S. M., INTLAB - INTerval LABoratory, T. Csendes Developments in Reliable Computing Kluwer Academic Publishers, Dordrecht (1999), 77-104. Available at http://www.ti3.tu-harburg.de/rump/intlab/. (1999) Zbl0949.65046
  23. Rump, S. M., 10.1017/S096249291000005X, Acta Numerica 19 (2010), 287-449. (2010) Zbl1323.65046MR2652784DOI10.1017/S096249291000005X
  24. Sakaguchi, H., Brand, H. R., 10.1016/0167-2789(96)00077-2, Physica D 97 (1996), 274-285. (1996) DOI10.1016/0167-2789(96)00077-2
  25. Tucker, W., Validated Numerics. A Short Introduction to Rigorous Computations, Princeton University Press, Princeton (2011). (2011) Zbl1231.65077MR2807595
  26. Berg, J. B. van den, Groothedde, C. M., Lessard, J.-P., A general method for computer-assisted proofs of periodic solutions in delay differential problems, Preprint (2018). (2018) MR3896998
  27. Berg, J. B. van den, Lessard, J.-P., 10.1090/noti1276, Notices Am. Math. Soc. 62 (2015), 1057-1061. (2015) Zbl1338.68301MR3444942DOI10.1090/noti1276
  28. Berg, J. B. van den, Williams, J. F., 10.1088/1361-6544/aa60e8, Nonlinearity 30 (2017), 1584-1638. (2017) Zbl1366.65068MR3636312DOI10.1088/1361-6544/aa60e8
  29. Loan, C. F. Van, 10.1137/1.9781611970999, Frontiers in Applied Mathematics 10, SIAM, Philadelphia (1992). (1992) Zbl0757.65154MR1153025DOI10.1137/1.9781611970999
  30. Wilczak, D., Zgliczynski, P., 10.1007/s00220-002-0709-0, Commun. Math. Phys. 234 (2003), 37-75. (2003) Zbl1055.70005MR1961956DOI10.1007/s00220-002-0709-0
  31. Zgliczyński, P., Rigorous numerics for dissipative PDEs. III: An effective algorithm for rigorous integration of dissipative PDEs, Topol. Methods Nonlinear Anal. 36 (2010), 197-262. (2010) Zbl1230.65113MR2788972
  32. Zgliczyński, P., Mischaikow, K., 10.1007/s102080010010, Found. Comput. Math. 1 (2001), 255-288. (2001) Zbl0984.65101MR1838755DOI10.1007/s102080010010

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.