×

Computing semigroups with error control. (English) Zbl 1520.65033

Summary: We develop an algorithm that computes strongly continuous semigroups on infinite-dimensional Hilbert spaces with explicit error control. Given a generator \(A\), a time \(t>0\), an arbitrary initial vector \(u_0\), and an error tolerance \(\epsilon>0\), the algorithm computes \(\exp(tA)u_0\) with error bounded by \(\epsilon\). The algorithm is based on a combination of a regularized functional calculus, suitable contour quadrature rules, and the adaptive computation of resolvents in infinite dimensions. As a particular case, we show that it is possible, even when only allowing pointwise evaluation of coefficients, to compute, with error control, semigroups on the unbounded domain \(L^2(\mathbb{R}^d)\) that are generated by partial differential operators with polynomially bounded coefficients of locally bounded total variation. For analytic semigroups (and more general Laplace transform inversion), we provide a quadrature rule whose error decreases like \(\exp(-cN/\log(N))\) for \(N\) quadrature points, that remains stable as \(N\rightarrow\infty\), and which is also suitable for infinite-dimensional operators. Numerical examples are given, including Schrödinger and wave equations on the aperiodic Ammann-Beenker tiling, complex perturbed fractional diffusion equations on \(L^2(\mathbb{R})\), and damped Euler-Bernoulli beam equations.

MSC:

65J08 Numerical solutions to abstract evolution equations
47A10 Spectrum, resolvent
46N40 Applications of functional analysis in numerical analysis

References:

[1] A. H. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33 (2011), pp. 488-511. · Zbl 1234.65028
[2] X. Antoine, A. Arnold, C. Besse, M. Ehrhardt and A. Schädle, A review of transparent and artificial boundary conditions techniques for linear and nonlinear Schrödinger equations, Comm. Math. Phys., 4 (2008), pp. 729-796. · Zbl 1364.65178
[3] W. Arendt, C. J. K. Batty, M. Hieber, and F. Neubrander, Cauchy problems, in Vector-Valued Laplace Transforms and Cauchy Problems, Springer, New York, 2001, pp. 109-240. · Zbl 0978.34001
[4] A. Arnold, M. Ehrhardt, and I. Sofronov, Discrete transparent boundary conditions for the Schrödinger equation: Fast calculation, approximation, and stability, Commun. Math. Sci., 1 (2003), pp. 501-556. · Zbl 1085.65513
[5] C. Batty, Unbounded operators: Functional calculus, generation, perturbations, Extracta Math., 24 (2009), pp. 99-133. · Zbl 1210.47043
[6] C. Batty, M. Haase, and J. Mubeen, The holomorphic functional calculus approach to operator semigroups, Acta Sci. Math.(Szeged), 79 (2013), pp. 289-323. · Zbl 1299.47034
[7] S. Becker and A. Hansen, Computing Solutions of Schrödinger Equations on Unbounded Domains - On the Brink of Numerical Algorithms, arXiv preprint, 2020, https://arxiv.org/abs/2010.16347.
[8] J. Ben-Artzi, M. J. Colbrook, A. C. Hansen, O. Nevanlinna, and M. Seidel, Computing Spectra – On the Solvability Complexity Index Hierarchy and Towers of Algorithms, preprint, 2020, https://arxiv.org/abs/1508.03280v5.
[9] L. Blum, F. Cucker, M. Shub, S. Smale, and R. M. Karp, Complexity and Real Computation, Springer, New York, 1998. · Zbl 0872.68036
[10] M. Blümlinger and R. F. Tichy, Topological algebras of functions of bounded variation I, Manuscripta Math., 65 (1989), pp. 245-255. · Zbl 0702.46037
[11] J. P. Boyd, Spectral methods using rational basis functions on an infinite interval, J. Comput. Phys., 69 (1987), pp. 112-142. · Zbl 0615.65090
[12] F. Bréhard, N. Brisebarre, and M. Joldeş, Validated and numerically efficient Chebyshev spectral methods for linear ordinary differential equations, ACM Trans. Math. Software, 44 (2018), pp. 1-42. · Zbl 1484.65155
[13] P. Brenner and V. Thomée, On rational approximations of semigroups, SIAM J. Numer. Anal., 16 (1979), pp. 683-694. · Zbl 0413.41011
[14] Y. Bruned and K. Schratz, Resonance Based Schemes for Dispersive Equations via Decorated Trees, preprint, 2020, https://arxiv.org/abs/2005.01649. · Zbl 1504.65168
[15] J. Butcher, On the numerical inversion of Laplace and Mellin transforms, in Proceedings of the Conference on Data Processing and Automatic Computing Machines, Salisbury, Australia, 1957, pp. 117-1.
[16] M. J. Colbrook, On the Computation of Geometric Features of Spectra of Linear Operators on Hilbert Spaces, arXiv preprint, 2019, https://arxiv.org/abs/1908.09598.
[17] M. J. Colbrook, The Foundations of Infinite-Dimensional Spectral Computations, PhD thesis, University of Cambridge, 2020.
[18] M. J. Colbrook, Computing spectral measures and spectral types, Comm. Math. Phys., 384 (2021), pp. 433-501. · Zbl 07348142
[19] M. J. Colbrook, V. Antun, and A. Hansen, Can Stable and Accurate Neural Networks Be computed? - On the Barriers of Deep Learning and Smale’s \(18\) th Problem, preprint, 2021, https://arxiv.org/abs/2101.08286.
[20] M. J. Colbrook and A. C. Hansen, The Foundations of Spectral Computations via the Solvability Complexity Index Hierarchy: Part I, arXiv preprint, 2019, https://arxiv.org/abs/1908.09592.
[21] M. J. Colbrook and A. C. Hansen, On the infinite-dimensional QR algorithm, Numer. Math., 143 (2019), pp. 17-83. · Zbl 1530.65055
[22] M. J. Colbrook, A. Horning, and A. Townsend, Computing spectral measures of self-adjoint operators, SIAM Rev., 63 (2021), pp. 489-524. · Zbl 07379587
[23] M. J. Colbrook, B. Roman, and A. C. Hansen, How to compute spectra with error control, Phys. Rev. Lett., 122 (2019), 250201.
[24] M. Crouzeix, S. Larsson, S. Piskarev, and V. Thomée, The stability of rational approximations of analytic semigroups, BIT, 33 (1993), pp. 74-84. · Zbl 0783.65050
[25] A. Dean͂o, D. Huybrechs, and A. Iserles, Computing Highly Oscillatory Integrals, SIAM, Philadelphia, 2017.
[26] K. Diethelm, The Analysis of Fractional Differential Equations: An Application-Oriented Exposition Using Differential Operators of Caputo Type, Springer, New York, 2010. · Zbl 1215.34001
[27] B. Dingfelder and J. A. C. Weideman, An improved Talbot method for numerical Laplace transform inversion, Numer. Algorithms, 68 (2015), pp. 167-183. · Zbl 1432.65190
[28] T. A. Driscoll, N. Hale, and L. N. Trefethen, Chebfun Guide, Pafunty Publications, Oxford, 2014.
[29] K.-J. Engel and R. Nagel, One-Parameter Semigroups for Linear Evolution Equations, Springer Science & Business Media, New York, 1999.
[30] B. Engquist and A. Majda, Absorbing boundary conditions for numerical simulation of waves, Proc. Natl. Acad. Sci. USA, 74 (1977), pp. 1765-1766. · Zbl 0378.76018
[31] B. Engquist and A. Majda, Radiation boundary conditions for acoustic and elastic wave calculations, Comm. Pure Appl. Math., 32 (1979), pp. 313-357. · Zbl 0387.76070
[32] H. O. Fattorini, Second Order Linear Differential Equations in Banach Spaces, Elsevier, New York, 2011.
[33] C. Fefferman and L. Seco, On the energy of a large atom, Bull. Amer. Math. Soc. (N.S.), 23 (1990), pp. 525-530. · Zbl 0722.35072
[34] C. Fefferman and L. Seco, Interval arithmetic in quantum mechanics, in Applications of Interval Computations (El Paso, TX, 1995), 1996, pp. 145-167. · Zbl 0841.65067
[35] R. Garrappa and M. Popolizio, Evaluation of generalized Mittag-Leffler functions on the real line, Adv. Comput. Math., 39 (2013), pp. 205-225. · Zbl 1272.33020
[36] I. Gavrilyuk, V. Makarov, and V. Vasylyk, Exponentially Convergent Algorithms for Abstract Differential Equations, Springer Science & Business Media, New York, 2011. · Zbl 1225.47001
[37] I. Gavrilyuk and V. L. Makarov, Exponentially convergent parallel discretization methods for the first order evolution equations, Comput. Methods Appl. Math., 1 (2001), pp. 333-355. · Zbl 0998.65056
[38] M. A. Gilles and A. Townsend, Continuous analogues of Krylov subspace methods for differential operators, SIAM J. Numer. Anal., 57 (2019), pp. 899-924. · Zbl 1411.65047
[39] T. Göckler and V. Grimm, Convergence analysis of an extended Krylov subspace method for the approximation of operator functions in exponential integrators, SIAM J. Numer. Anal., 51 (2013), pp. 2189-2213. · Zbl 1278.65076
[40] J. S. Green, The Calculation of the Time-Responses of Linear Systems, PhD thesis, Department of Applied Mathematics, Imperial College London, 1955.
[41] V. Grimm, Resolvent Krylov subspace approximation to operator functions, BIT, 52 (2012), pp. 639-659. · Zbl 1258.65052
[42] N. Hale, N. J. Higham, and L. N. Trefethen, Computing \(A^{\alpha}, \log(A)\), and related matrix functions by contour integrals, SIAM J. Numer. Anal., 46 (2008), pp. 2505-2523. · Zbl 1176.65053
[43] T. C. Hales, A proof of the Kepler conjecture, Ann. of Math. (2), 162 (2005), pp. 1065-1185. · Zbl 1096.52010
[44] A. Hansen, On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc., 24 (2011), pp. 81-124. · Zbl 1210.47013
[45] N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1179-1193. · Zbl 1081.65037
[46] M. Hochbruck and A. Ostermann, Exponential integrators, Acta Numer., 19 (2010), pp. 209-286. · Zbl 1242.65109
[47] A. Horning and A. Townsend, FEAST for differential eigenvalue problems, SIAM J. Numer. Anal., 58 (2020), pp. 1239-1262. · Zbl 1439.65088
[48] A. Iserles, K. Kropielnicka, and P. Singh, Magnus-Lanczos methods with simplified commutators for the Schrödinger equation with a time-dependent potential, SIAM J. Numer. Anal., 56 (2018), pp. 1547-1569. · Zbl 1395.65102
[49] A. Iserles and M. Webb, A family of orthogonal rational functions and other orthogonal systems with a skew-Hermitian differentiation matrix, J. Fourier Anal. Appl., 26 (2020), p. 19. · Zbl 1459.42006
[50] T. Janssen, G. Chapuis, and M. De Boissieu, Aperiodic Crystals: From Modulated Phases to Quasicrystals: Structure and Properties, Oxford University Press, Oxford, 2018. · Zbl 1416.82003
[51] D. Johnstone, M. J. Colbrook, A. Nielsen, P. Öhberg, and C. W. Duncan, Bulk Localised Transport States in Infinite and Finite Quasicrystals via Magnetic Aperiodicity, preprint, 2021, https://arxiv.org/abs/2107.05635.
[52] T. Kato, Perturbation Theory for Linear Operators, Springer, New York, 2013.
[53] K. Kormann, C. Lasser, and A. Yurova, Stable interpolation with isotropic and anisotropic Gaussians using Hermite generating function, SIAM J. Sci. Comput., 41 (2019), pp. 3839-3859. · Zbl 07141501
[54] C. Lasser and C. Lubich, Computing quantum dynamics in the semiclassical regime, Acta Numer., 29 (2020), pp. 229-401. · Zbl 07674564
[55] X. Li and C. Xu, A space-time spectral method for the time fractional diffusion equation, SIAM J. Numer. Anal., 47 (2009), pp. 2108-2131. · Zbl 1193.35243
[56] J. Liesen and Z. Strakos, Krylov Subspace Methods: Principles and Analysis, Oxford University Press, Oxford, 2013. · Zbl 1263.65034
[57] K. Liu, S. Chen, and Z. Liu, Spectrum and stability for elastic systems with global or local Kelvin-Voigt damping, SIAM J. Appl. Math., 59 (1998), pp. 651-668. · Zbl 0924.35018
[58] M. López-Fernández and C. Palencia, On the numerical inversion of the Laplace transform of certain holomorphic mappings, Appl. Numer. Math., 51 (2004), pp. 289-303. · Zbl 1059.65120
[59] M. López-Fernández, C. Palencia, and A. Schädle, A spectral order method for inverting sectorial Laplace transforms, SIAM J. Numer. Anal., 44 (2006), pp. 1332-1350. · Zbl 1124.65120
[60] C. Lubich, From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis, Zur. Lect. Adv. Math, European Mathematical Society, Zürich, 2008. · Zbl 1160.81001
[61] C. Lubich, On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations, Math. Comp., 77 (2008), pp. 2141-2153. · Zbl 1198.65186
[62] F. Mainardi and R. Gorenflo, On Mittag-Leffler-type functions in fractional evolution processes, J. Comput. Appl. Math., 118 (2000), pp. 283-299. · Zbl 0970.45005
[63] R. I. McLachlan and G. R. W. Quispel, Splitting methods, Acta Numer., 11 (2002), pp. 341-434. · Zbl 1105.65341
[64] W. McLean and V. Thomée, Time discretization of an evolution equation via Laplace transforms, IMA J. Appl. Math., 24 (2004), pp. 439-463. · Zbl 1068.65146
[65] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conf. Ser. in Appl. Math. 63, SIAM, Philadelphia, 1992. · Zbl 0761.65002
[66] S. Olver, GMRES for the differentiation operator, SIAM J. Numer. Anal., 47 (2009), pp. 3359-3373. · Zbl 1202.65036
[67] S. Olver, ApproxFun.jl, version 0.8, Github, 2018.
[68] S. Olver and A. Townsend, A fast and well-conditioned spectral method, SIAM Rev., 55 (2013), pp. 462-489. · Zbl 1273.65182
[69] S. Olver and A. Townsend, A practical framework for infinite-dimensional linear algebra, in Proceedings of the 1st First Workshop for High Performance Technical Computing in Dynamic Languages, IEEE Press, 2014, pp. 57-62.
[70] S. Olver and M. Webb, SpectralMeasures.jl, Github, 2018.
[71] A. Ostermann and C. Su, Two exponential-type integrators for the “good” Boussinesq equation, Numer. Math., 143 (2019), pp. 683-712. · Zbl 1428.35425
[72] C. Palencia, A stability result for sectorial operators in Banach spaces, SIAM J. Numer. Anal., 30 (1993), pp. 1373-1384. · Zbl 0794.65053
[73] H.-K. Pang and H.-W. Sun, Fast numerical contour integral method for fractional diffusion equations, J. Sci. Comput., 66 (2016), pp. 41-66. · Zbl 1351.65058
[74] A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations, Springer Science & Business Media, New York, 2012. · Zbl 0516.47023
[75] S. Roche, G. Trambly de Laissardière, and D. Mayou, Electronic transport properties of quasicrystals, J. Math. Phys., 38 (1997), pp. 1794-1822. · Zbl 0876.73061
[76] F. Rousset and K. Schratz, A general framework of low regularity integrators, SIAM J. Numer. Anal., 59 (2021), pp. 1735-1768. · Zbl 1486.65127
[77] S. M. Rump, Verification methods: Rigorous results using floating-point arithmetic, Acta Numer., 19 (2010), pp. 287-449. · Zbl 1323.65046
[78] D. Shechtman, I. Blech, D. Gratias, and J. W. Cahn, Metallic phase with long-range orientational order and no translational symmetry, Phys. Rev. Lett., 53 (1984), pp. 1951-1953.
[79] D. Sheen, I. H. Sloan, and V. Thomée, A parallel method for time discretization of parabolic equations based on Laplace transformation and quadrature, IMA J. Numer. Anal., 23 (2003), pp. 269-299. · Zbl 1022.65108
[80] V. Simoncini and D. B. Szyld, Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14 (2007), pp. 1-59. · Zbl 1199.65112
[81] Z. M. Stadnik, Physical Properties of Quasicrystals, Springer, New York, 2012.
[82] J. Szeftel, Design of absorbing boundary conditions for Schrödinger equations in \(\mathbb{R}^d\), SIAM J. Numer. Anal., 42 (2004), pp. 1527-1551. · Zbl 1094.35037
[83] A. Talbot, The accurate numerical inversion of Laplace transforms, IMA J. Appl. Math., 23 (1979), pp. 97-120. · Zbl 0406.65054
[84] A. Townsend and L. N. Trefethen, Continuous analogues of matrix factorizations, Proc. A, 471 (2015), 20140585. · Zbl 1372.65095
[85] L. N. Trefethen and J. A. C. Weideman, The exponentially convergent trapezoidal rule, SIAM Rev., 56 (2014), pp. 385-458. · Zbl 1307.65031
[86] L. N. Trefethen, J. A. C. Weideman, and T. Schmelzer, Talbot quadratures and rational approximations, BIT, 46 (2006), pp. 653-670. · Zbl 1103.65030
[87] S. V. Tsynkov, Numerical solution of problems on unbounded domains. A review, Appl. Numer. Math., 27 (1998), pp. 465-532. · Zbl 0939.76077
[88] W. Tucker, Validated Numerics: A Short Introduction to Rigorous Computations, Princeton University Press, Princeton, NJ, 2011. · Zbl 1231.65077
[89] M. Webb, Isospectral Algorithms, Toeplitz Matrices and Orthogonal Polynomials, PhD thesis, University of Cambridge, 2017.
[90] M. Webb and S. Olver, Spectra of Jacobi operators via connection coefficient matrices, Comm. Math. Phys., 382 (2021), pp. 657-707. · Zbl 1518.47055
[91] J. A. C. Weideman, Computation of the complex error function, SIAM J. Numer. Anal., 31 (1994), pp. 1497-1518. · Zbl 0832.65011
[92] J. A. C. Weideman, Improved contour integral methods for parabolic PDEs, IMA J. Numer. Anal., 30 (2010), pp. 334-350. · Zbl 1186.65125
[93] J. A. C. Weideman, Gauss-Hermite quadrature for the Bromwich integral, SIAM J. Numer. Anal., 57 (2019), pp. 2200-2216. · Zbl 1420.65134
[94] J. A. C. Weideman and L. N. Trefethen, Parabolic and hyperbolic contours for computing the Bromwich integral, Math. Comp., 76 (2007), pp. 1341-1356. · Zbl 1113.65119
[95] T.-J. Xiao and J. Liang, The Cauchy Problem for Higher Order Abstract Differential Equations, Springer, New York, 2013.
[96] F. Zeng, F. Liu, C. Li, K. Burrage, I. Turner, and V. Anh, A Crank-Nicolson ADI spectral method for a two-dimensional Riesz space fractional nonlinear reaction-diffusion equation, SIAM J. Numer. Anal., 52 (2014), pp. 2599-2622. · Zbl 1382.65349
[97] G.-D. Zhang and B.-Z. Guo, On the spectrum of Euler-Bernoulli beam equation with Kelvin-Voigt damping, J. Math. Anal. Appl., 374 (2011), pp. 210-229. · Zbl 1205.35176
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.