Exponential Sum Approximations for t^−β

Abstract

Given β > 0 and δ > 0, the function t ^−β may be approximated for t in a compact interval [δ, T] by a sum of terms of the form we^−at, with parameters w > 0 and a > 0. One such an approximation, studied by Beylkin and Monzón (Appl. Comput. Harmon. Anal. 28:131–149, 2010), is obtained by applying the trapezoidal rule to an integral representation of t ^−β, after which Prony’s method is applied to reduce the number of terms in the sum with essentially no loss of accuracy. We review this method, and then describe a similar approach based on an alternative integral representation. The main difference is that the new approach achieves much better results before the application of Prony’s method; after applying Prony’s method the performance of both is much the same.

Dedicated to Ian H. Sloan on the occasion of his 80th birthday.

1 Introduction

Consider a Volterra operator with a convolution kernel,

$$\displaystyle \begin{aligned} \mathbb{K}u(t)=(k*u)(t)=\int_0^t k(t-s)u(s)\,ds\quad \text{for }t>0, \end{aligned} $$

(1)

and suppose that we seek a numerical approximation to $\mathbb {K}u$ at the points of a grid $0=t_0<t_1<t_2<\cdots <t_{N_t}=T$. For example, if we know U ⁿ ≈ u(t _n) and define (for simplicity) a piecewise-constant interpolant $\tilde U(t)=U^n$ for t ∈ I _n = (t _n−1, t _n), then

$$\displaystyle \begin{aligned} \mathbb{K}u(t_n)\approx\mathbb{K}\tilde U(t_n) =\sum_{j=1}^n\omega_{nj}U^j\quad \text{where}\quad \omega_{nj}=\int_{I_j}k(t_n-s)\,ds. \end{aligned}$$

The number of operations required to compute this sum in the obvious way for 1 ≤ n ≤ N _t is proportional to $\sum _{n=1}^{N_t}n\approx N_t^2/2$, and this quadratic growth can be prohibitive in applications where each U ^j is a large vector and not just a scalar. Moreover, it might not be possible to store U ^j in active memory for all time levels j.

These problems can be avoided using a simple, fast algorithm if the kernel k admits an exponential sum approximation

$$\displaystyle \begin{aligned} k(t)\approx\sum_{l=1}^L w_le^{b_lt}\quad \text{for }\delta\le t\le T, \end{aligned} $$

(2)

provided sufficient accuracy is achieved using only a moderate number of terms L, for a choice of δ > 0 that is smaller than the time step Δt _n = t _n − t _n−1 for all n. Indeed, if Δt _n ≥ δ then δ ≤ t _n − s ≤ T for 0 ≤ s ≤ t _n−1 so

$$\displaystyle \begin{aligned} \sum_{j=1}^{n-1}\omega_{nj}U^j=\int_0^{t_{n-1}}k(t_n-s)\tilde U(s)\,ds \approx\int_0^{t_{n-1}}\sum_{l=1}^Lw_le^{b_l(t_n-s)} \tilde U(s)\,ds=\sum_{l=1}^L\varTheta^n_l, \end{aligned}$$

where

$$\displaystyle \begin{aligned} \varTheta^n_l=w_l\int_0^{t_{n-1}}e^{b_l(t_n-s)}\tilde U(s)\,ds =\sum_{j=1}^{n-1}\kappa_{lnj}U^j \quad \text{and}\quad \kappa_{lnj}=w_l\int_{I_j}e^{b_l(t_n-s)}\,ds. \end{aligned}$$

Thus,

$$\displaystyle \begin{aligned} \mathbb{K}\tilde U(t_n)\approx\omega_{nn}U^n+\sum_{l=1}^L\varTheta^n_l, \end{aligned} $$

(3)

and by using the recursive formula

$$\displaystyle \begin{aligned} \varTheta^n_l=\kappa_{ln,n-1}U^{n-1}+e^{b_l\varDelta t_n}\varTheta^{n-1}_l \quad \text{for }n\ge2,\quad \text{with }\varTheta^1_l=0, \end{aligned}$$

we can evaluate $\mathbb {K}\tilde U(t_n)$ for 1 ≤ n ≤ N to an acceptable accuracy with a number of operations proportional to LN _t—a substantial saving if L ≪ N _t. In addition, we may overwrite $\varTheta ^{n-1}_l$ with $\varTheta ^n_l$, and overwrite U ⁿ⁻¹ with U ⁿ, so that the active storage requirement is proportional to L instead of N _t.

In the present work, we study two exponential sum approximations to the kernel k(t) = t ^−β with β > 0. Our starting point is the integral representation

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}=\frac{1}{\varGamma(\beta)}\int_0^\infty e^{-pt}p^\beta \,\frac{dp}{p}\quad \text{for }t>0\mbox{ and }\beta>0, \end{aligned} $$

(4)

which follows easily from the integral definition of the Gamma function via the substitution p = y∕t (if y is the original integration variable). Section 2 discusses the results of Beylkin and Monzón [3], who used the substitution p = e ^x in (4) to obtain

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}=\frac{1}{\varGamma(\beta)}\int_{-\infty}^\infty \exp(-te^x+\beta x)\,dx. \end{aligned} $$

(5)

Applying the infinite trapezoidal rule with step size h > 0 leads to the approximation

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}\approx\frac{1}{\varGamma(\beta)}\sum_{n=-\infty}^\infty w_ne^{-a_nt} \end{aligned} $$

(6)

where

$$\displaystyle \begin{aligned} a_n=e^{hn}\quad \text{and}\quad w_n=he^{\beta nh}. \end{aligned} $$

(7)

We will see that the relative error,

$$\displaystyle \begin{aligned} \rho(t)=1-\frac{t^\beta}{\varGamma(\beta)}\sum_{n=-\infty}^\infty w_ne^{-a_nt}, \end{aligned} $$

(8)

satisfies a uniform bound for 0 < t < ∞. If t is restricted to a compact interval [δ, T] with 0 < δ < T < ∞, then we can similarly bound the relative error in the finite exponential sum approximation

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}\approx\frac{1}{\varGamma(\beta)}\sum_{n=-M}^N w_ne^{-a_nt}\quad \text{for }\delta\le t\le T, \end{aligned} $$

(9)

for suitable choices of M > 0 and N > 0.

The exponents a _n = e ^nh in the sum (9) tend to zero as n →−∞. In Sect. 3 we see how, for a suitable threshold exponent size a ^∗, Prony’s method may be used to replace $\sum _{a_n\le a^*}w_ne^{-a_nt}$ with an exponential sum having fewer terms. This idea again follows Beylkin and Monzón [3], who discussed it in the context of approximation by Gaussian sums.

Section 4 introduces an alternative approach based on the substitution $p=\exp (x-e^{-x})$, which transforms (4) into the integral representation

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}=\frac{1}{\varGamma(\beta)}\int_{-\infty}^\infty \exp\bigl(-\varphi(x,t)\bigr)(1+e^{-x})\,dx, \end{aligned} $$

(10)

where

$$\displaystyle \begin{aligned} \varphi(x,t)=tp-\beta\log p=t\exp(x-e^{-x})-\beta(x-e^{-x}). \end{aligned} $$

(11)

Applying the infinite trapezoidal rule again leads to an approximation of the form (6), this time with

$$\displaystyle \begin{aligned} a_n=\exp\bigl(nh-e^{-nh}\bigr)\quad \text{and}\quad w_n=h(1+e^{-nh})\exp\bigl(\beta(nh-e^{-nh})\bigr). \end{aligned} $$

(12)

As x →∞, the integrands in both (5) and (10) decay like $\exp (-te^x)$. However, they exhibit different behaviours as x →−∞, with the former decaying like e ^βx = e ^−β|x| whereas the latter decays much faster, like $\exp (-\beta e^{-x})=\exp (-\beta e^{|x|})$, as seen in Fig. 1 (note the differing scales on the vertical axis).

Fig. 1

Top: the integrand from (10) when β = 1∕2 for different t. Bottom: comparison between the integrands from (5) and (10) when t = 0.01; the dashed line is the former and the solid line the latter

Li [5] summarised several alternative approaches for fast evaluation of a fractional integral of order α, that is, for an integral operator of the form (1) with kernel

$$\displaystyle \begin{aligned} k(t)=\frac{t^{\alpha-1}}{\varGamma(\alpha)}=\frac{\sin\pi\alpha}{\pi} \int_0^\infty e^{-pt}p^{-\alpha}\,dp \quad \text{for }0<\alpha<1\mbox{ and }t>0, \end{aligned} $$

(13)

where the integral representation follows from (4), with β = 1 − α, and the reflection formula for the Gamma function, $\varGamma (\alpha )\varGamma (1-\alpha )=\pi /\sin \pi \alpha$. She developed a quadrature approximation,

$$\displaystyle \begin{aligned} \int_0^\infty e^{-pt}p^{-\alpha}\,dp\approx\sum_{j=1}^Q w_je^{-p_jt}p_j^{-\alpha}\quad \text{for }\delta\le t<\infty, \end{aligned} $$

(14)

which again provides an exponential sum approximation, and showed that the error can be made smaller than 𝜖 for all t ∈ [δ, ∞) with Q of order $(\log \epsilon ^{-1}+\log \delta ^{-1})^2$.

More recently, Jiang et al. [4] developed an exponential sum approximation for t ∈ [δ, T] using composite Gauss quadrature on dyadic intervals, applied to (5), with Q of order

$$\displaystyle \begin{aligned} (\log\epsilon^{-1})\log\bigl(T\delta^{-1}\log\epsilon^{-1}\bigr) +(\log\delta^{-1})\log\bigl(\delta^{-1}\log\epsilon^{-1}\bigr). \end{aligned}$$

In other applications, the kernel k(t) is known via its Laplace transform,

$$\displaystyle \begin{aligned} \hat k(z)=\int_0^\infty e^{-zt}k(t)\,dt, \end{aligned}$$

so that instead of the exponential sum (2) it is natural to seek a sum-of-poles approximation,

$$\displaystyle \begin{aligned} \hat k(z)\approx\sum_{l=1}^L\frac{w_l}{z-b_l} \end{aligned}$$

for z in a suitable region of the complex plane; see, for instance, Alpert et al. [2] and Xu and Jian [7].

2 Approximation Based on the Substitution p = e ^x

The nature of the approximation (6) is revealed by a remarkable formula for the relative error [3, Section 2]. For completeness, we outline the proof.

Theorem 1

If the exponents and weights are given by (7), then the relative error (8) has the representation

$$\displaystyle \begin{aligned} \rho(t)=-2\sum_{n=1}^\infty R(n/h)\cos\bigl(2\pi(n/h)\log t -\varPhi(n/h)\bigr) \end{aligned} $$

(15)

where R(ξ) and Φ(ξ) are the real-valued functions defined by

$$\displaystyle \begin{aligned} \frac{\varGamma(\beta+i2\pi\xi)}{\varGamma(\beta)}=R(\xi)e^{i\varPhi(\xi)} \quad \mathit{\text{with }}R(\xi)>0\mathit{\mbox{ and }}\varPhi(0)=0. \end{aligned}$$

Moreover, $R(\xi )\le e^{-2\pi \theta |\xi |}/(\cos \theta )^\beta$ for 0 ≤ θ < π∕2 and −∞ < ξ < ∞.

Proof

For each t > 0, the integrand $f(x)=\exp (-te^x+\beta x)$ from (5) belongs to the Schwarz class of rapidly decreasing C ^∞ functions, and we may therefore apply the Poisson summation formula to conclude that

$$\displaystyle \begin{aligned} h\sum_{n=-\infty}^\infty f(nh)=\sum_{n=-\infty}^\infty\tilde f(n/h) =\int_{-\infty}^\infty f(x)\,dx+\sum_{n\ne0}\tilde f(n/h), \end{aligned}$$

where the Fourier transform of f is

$$\displaystyle \begin{aligned} \tilde f(\xi)=\int_{-\infty}^\infty e^{-i2\pi\xi x}f(x)\,dx =\int_{-\infty}^\infty\exp\bigl(-te^x+(\beta-i2\pi\xi)x\bigr)\,dx. \end{aligned}$$

The substitution p = te ^x gives

$$\displaystyle \begin{aligned} \tilde f(\xi)=\frac{1}{t^{\beta-i2\pi\xi}}\int_0^\infty e^{-p}p^{\beta-i2\pi\xi}\,\frac{dp}{p} =\frac{\varGamma(\beta-i2\pi\xi)}{t^{\beta-i2\pi\xi}}, \end{aligned}$$

so, with a _n and w _n defined by (7),

$$\displaystyle \begin{aligned} \frac{1}{\varGamma(\beta)} \sum_{n=-\infty}^\infty w_ne^{-a_nt} =\frac{1}{t^\beta}+\frac{1}{t^\beta}\sum_{n\ne0} \frac{\varGamma(\beta-i2\pi n/h)}{\varGamma(\beta)}\,t^{i2\pi n/h}. \end{aligned}$$

The formula for ρ(t) follows after noting that $\overline {\varGamma (\beta +i2\pi \xi )}=\varGamma (\beta -i2\pi \xi )$ for all real ξ; hence, R(−ξ) = R(ξ) and Φ(−ξ) = −Φ(ξ).

To estimate R(ξ), let y > 0 and define the ray $\mathbb {C}_\theta =\{se^{i\theta }:0<s<\infty \}$. By Cauchy’s theorem,

$$\displaystyle \begin{aligned} \varGamma(\beta+iy)=\int_{\mathbb{C}_\theta}e^{-p}p^{\beta+iy}\,\frac{dp}{p} =\int_0^\infty e^{-se^{i\theta}}(se^{i\theta})^{\beta+iy}\, \frac{ds}{s} \end{aligned}$$

and thus

$$\displaystyle \begin{aligned} |\varGamma(\beta+iy)|\le\int_0^\infty e^{-s\cos\theta}e^{-\theta y} s^\beta\,\frac{ds}{s}=\frac{e^{-\theta y}}{(\cos\theta)^\beta} \int_0^\infty e^{-s}s^\beta\,\frac{ds}{s} =\frac{e^{-\theta y}}{(\cos\theta)^\beta}\,\varGamma(\beta), \end{aligned}$$

implying the desired bound for R(ξ). □

In practice, the amplitudes R(n∕h) decay so rapidly with n that only the first term in the expansion (15) is significant. For instance, since [1, 6.1.30]

$$\displaystyle \begin{aligned} \bigl|\varGamma(\tfrac12+iy)\bigr|{}^2=\frac{\pi}{\cosh(\pi y)}, \end{aligned}$$

if β = 1∕2 then $R(\xi )=(\cosh 2\pi ^2\xi )^{-1/2}\le \sqrt {2}e^{-\pi ^2\xi }$ so, choosing h = 1∕3, we have R(1∕h) = 1.95692 × 10⁻¹³ and R(2∕h) = 2.70786 × 10⁻²⁶. In general, the bound $R(n/h)\le e^{-2\pi \theta n/h}/(\cos \theta )^\beta$ from the theorem is minimized by choosing $\tan \theta =2\pi n/(\beta h)$, implying that

$$\displaystyle \begin{aligned} R(n/h)\le\bigl(1+(r_n/\beta)^2\bigr)^{\beta/2} \exp\bigl(-r_n\arctan(r_n/\beta)\bigr) \quad \text{where }r_n=2\pi n/h. \end{aligned}$$

Since we can evaluate only a finite exponential sum, we now estimate the two tails of the infinite sum in terms of the upper incomplete Gamma function,

$$\displaystyle \begin{aligned} \varGamma(\beta,q)=\int_q^\infty e^{-p}p^\beta\,\frac{dp}{p} \quad \text{for }\beta>0~\mbox{and }q>0. \end{aligned}$$

Theorem 2

If the exponents and weights are given by (7), then

$$\displaystyle \begin{aligned} t^\beta\sum_{n=N+1}^\infty w_ne^{-a_nt}\le\varGamma(\beta,te^{Nh}) \quad \mathit{\text{provided }}te^{Nh}\ge\beta, \end{aligned}$$

and

$$\displaystyle \begin{aligned} t^\beta\sum_{n=-\infty}^{-M-1}w_ne^{-a_nt}\le\varGamma(\beta) -\varGamma(\beta,te^{-Mh}) \quad \mathit{\text{provided }}te^{-Mh}\le\beta. \end{aligned}$$

Proof

For each t > 0, the integrand $f(x)=\exp (-te^x+\beta x)$ from (5) decreases for $x>\log (\beta /t)$. Therefore, if $Nh\ge \log (\beta /t)$, that is, if te ^Nh ≥ β, then

$$\displaystyle \begin{aligned} t^\beta h\sum_{n=N+1}^\infty f(nh)\le t^\beta\int_{Nh}^\infty f(x)\,dx =\int_{te^{Nh}}^\infty e^{-p}p^\beta\,\frac{dp}{p} =\varGamma(\beta,te^{Nh}), \end{aligned}$$

where, in the final step, we used the substitution p = te ^x. Similarly, the function $f(-x)=\exp (-te^{-x}-\beta x)$ decreases for $x>\log (t/\beta )$ so if $Mh\ge \log (t/\beta )$, that is, if te ^−Mh ≤ β, then

$$\displaystyle \begin{aligned} t^\beta h\sum_{n=-\infty}^{-M-1}f(nh) =t^\beta h\sum_{n=M+1}^\infty f(-nh) \le t^\beta\int_{Mh}^\infty f(-x)\,dx =\int_0^{te^{-Mh}}e^{-p}p^\beta\,\frac{dp}{p}, \end{aligned}$$

where, in the final step, we used the substitution p = te ^−x. □

Given 𝜖 _RD > 0 there exists h > 0 such that

$$\displaystyle \begin{aligned} 2\sum_{n=1}^\infty|\varGamma(\beta+i2\pi n/h)| =\epsilon_{\text{RD}}\varGamma(\beta), \end{aligned} $$

(16)

and by Theorem 1,

$$\displaystyle \begin{aligned} |\rho(t)|\le\epsilon_{\text{RD}}\quad \text{for }0<t<\infty, \end{aligned}$$

so 𝜖 _RD is an upper bound for the relative discretization error. Similarly, given a sufficiently small 𝜖 _RT > 0, there exist x _δ > 0 and X _T > 0 such that $\delta e^{x_\delta }\ge \beta$ and $Te^{-X_T}\le \beta$ with

$$\displaystyle \begin{aligned} \varGamma(\beta,\delta e^{x_\delta})=\epsilon_{\text{RT}}\varGamma(\beta) \quad \text{and}\quad \varGamma(\beta)-\varGamma(\beta,Te^{-X_T}) =\epsilon_{\text{RT}}\varGamma(\beta). \end{aligned} $$

(17)

Thus, by Theorem 2,

$$\displaystyle \begin{aligned} \frac{t^\beta}{\varGamma(\beta)}\sum_{n=N+1}^\infty w_ne^{-a_nt} \le\epsilon_{\text{RT}} \quad \text{for }t\ge\delta~\mbox{and }Nh\ge x_\delta, \end{aligned}$$

and

$$\displaystyle \begin{aligned} \frac{t^\beta}{\varGamma(\beta)}\sum_{n=-\infty}^{-M-1}w_ne^{-a_nt} \le\epsilon_{\text{RT}} \quad \text{for }t\le T\mbox{ and }Mh\ge X_T, \end{aligned}$$

showing that 2𝜖 _RT is an upper bound for the relative truncation error. Denoting the overall relative error for the finite sum (9) by

$$\displaystyle \begin{aligned} \rho^N_M(t)=1-\frac{t^\beta}{\varGamma(\beta)}\sum_{n=-M}^Nw_ne^{-a_nt}, \end{aligned} $$

(18)

we therefore have

$$\displaystyle \begin{aligned} |\rho^N_M(t)|\le\epsilon_{\text{RD}}+2\epsilon_{\text{RT}} \quad \text{for }\delta\le t\le T, Nh\ge x_\delta\mbox{ and }Mh\ge X_T. \end{aligned} $$

(19)

The estimate for R(ξ) in Theorem 1, together with the asymptotic behaviours

$$\displaystyle \begin{aligned} \varGamma(\beta,q)\sim q^{\beta-1}e^{-q}\quad \text{as }q\to\infty, \end{aligned}$$

and

$$\displaystyle \begin{aligned} \varGamma(\beta)-\varGamma(\beta,q)\sim\frac{q^\beta}{\beta} \quad \text{as }q\to0, \end{aligned}$$

imply that (19) can be satisfied with

$$\displaystyle \begin{aligned} h^{-1}\ge C\log\epsilon_{\text{RD}}^{-1},\qquad N\ge Ch^{-1}\log(\delta^{-1}\log\epsilon_{\text{RT}}^{-1}),\qquad M\ge Ch^{-1}\log(T\epsilon_{\text{RT}}^{-1}). \end{aligned}$$

Figure 2 shows the relation between 𝜖 _RD and 1∕h given by (16), and confirms that 1∕h is approximately proportional to $\log \epsilon _{\text{RT}}^{-1}$. In Fig. 3, for each value of 𝜖 we computed h by solving (16) with 𝜖 _RD = 𝜖∕3, then computed x _δ and X _T by solving (17) with 𝜖 _RT = 𝜖∕3, and finally put M = ⌈X _T∕h⌉ and N = ⌈x _δ∕h⌉.

Fig. 2

The bound 𝜖 _RD for the relative discretization error, defined by (16), as a function of 1∕h for various choices of β

Fig. 3

The growth in M and N as the upper bound for the overall relative error (18) decreases, for different choices of T and δ

3 Prony’s Method

The construction of Sect. 2 leads to an exponential sum approximation (9) with many small exponents a _n. We will now explain how the corresponding terms can be aggregated to yield a more efficient approximation.

Consider more generally an exponential sum

$$\displaystyle \begin{aligned} g(t)=\sum_{l=1}^L w_le^{-a_lt}, \end{aligned}$$

in which the weights and exponents are all strictly positive. Our aim is to approximate this function by an exponential sum with fewer terms,

$$\displaystyle \begin{aligned} g(t)\approx\sum_{k=1}^K\tilde w_ke^{-\tilde a_kt},\quad 2K-1<L, \end{aligned}$$

whose weights $\tilde w_k$ and exponents $\tilde a_k$ are again all strictly positive. To this end, let

$$\displaystyle \begin{aligned} g_j=(-1)^jg^{(j)}(0)=\sum_{l=1}^L w_la_l^j. \end{aligned}$$

We can hope to find 2K parameters $\tilde w_k$ and $\tilde a_k$ satisfying the 2K conditions

$$\displaystyle \begin{aligned} g_j=\sum_{k=1}^K\tilde w_k\tilde a_k^j \quad \text{for }0\le j\le 2K-1, \end{aligned} $$

(20)

so that, by Taylor expansion,

$$\displaystyle \begin{aligned} g(t)\approx\sum_{j=0}^{2K-1}g_j\,\frac{(-t)^j}{j!} =\sum_{k=1}^K\tilde w_k\sum_{j=0}^{2K-1} \frac{(-\tilde a_kt)^j}{j!} \approx\sum_{k=1}^K\tilde w_ke^{-\tilde a_kt}. \end{aligned}$$

The approximations here require that the g _j and the $\tilde a_kt$ are nicely bounded, and preferably small.

Algorithm 1 Prony(a ₁, …, a _L, w ₁, …w _L, K)

Require: 2K − 1 ≤ L

Compute $g_j=\sum _{l=1}^Lw_la_l^j$ for 0 ≤ j ≤ 2K − 1

Find q ₀, …, q _K−1 satisfying $\sum _{m=0}^{K-1}g_{j+m}q_m=-g_{j+K}$ for 0 ≤ j ≤ K − 1, and put q _K = 1

Find the roots $\tilde a_1$, …, $\tilde a_K$ of the polynomial $Q(z)=\sum _{k=0}^K q_kz^k$

Find $\tilde w_1$, …, $\tilde w_K$ satisfying $\sum _{k=1}^K\tilde a_k^j\tilde w_k\approx g_j$ for 0 ≤ j ≤ 2K − 1

return $\tilde a_1$, …, $\tilde a_K$, $\tilde w_1$, …, $\tilde w_K$

In Prony’s method, we seek to satisfy (20) by introducing the monic polynomial

$$\displaystyle \begin{aligned} Q(z)=\prod_{k=1}^K(z-\tilde a_k)=\sum_{k=0}^K q_kz^k, \end{aligned}$$

and observing that the unknown coefficients q _k must satisfy

$$\displaystyle \begin{aligned} \sum_{m=0}^K g_{j+m}q_m=\sum_{m=0}^K\sum_{k=1}^K\tilde w_k \tilde a_k^{j+m}q_m=\sum_{k=1}^K\tilde w_k\tilde a_k^j \sum_{m=0}^Kq_m\tilde a_k^m =\sum_{k=1}^K\tilde w_k\tilde a_k^jQ(\tilde a_k)=0, \end{aligned}$$

for 0 ≤ j ≤ K − 1 (so that j + m ≤ 2K − 1 for 0 ≤ m ≤ K), with q _K = 1. Thus,

$$\displaystyle \begin{aligned} \sum_{m=0}^{K-1}g_{j+m}q_m=b_j,\quad \text{where }b_j=-g_{j+K}, \quad \text{for }0\le j\le K-1, \end{aligned}$$

which suggests the procedure Prony defined in Algorithm 1. We must, however, beware of several potential pitfalls:

• 1. the best choice for K is not clear;

• 2. the K × K matrix [g _j+k] might be badly conditioned;

• 3. the roots of the polynomial Q(z) might not all be real and positive;

• 4. the linear system for the $\tilde w_k$ is overdetermined, and the least-squares solution might have large residuals;

• 5. the $\tilde w_k$ might not all be positive.

We will see that nevertheless the algorithm can be quite effective, even when K = 1, in which case we simply compute

$$\displaystyle \begin{aligned} g_0=\sum_{l=1}^Lw_l,\quad g_1=\sum_{l=1}^Lw_la_l,\quad \tilde a_1=g_1/g_0,\quad \tilde w_1=g_0. \end{aligned}$$

Example 1

We took β = 3∕4, δ = 10⁻⁶, T = 10, 𝜖 = 10⁻⁸, 𝜖 _RD = 0.9 × 10⁻⁸ and 𝜖 _RT = 0.05 × 10⁻⁸. The methodology of Sect. 2 led to the choices h = 0.47962, M = 65 and N = 36, and we confirmed via direct evaluation of the relative error that $|\rho ^N_M(t)|\le 0.92\times 10^{-8}$ for δ ≤ t ≤ T. We applied Prony’s method to the first L terms of the sum in (9), that is, those with − M ≤ n ≤ L − M, thereby reducing the total number of terms by L − K. Table 1 lists, for different choices of L and K, the additional contribution to the relative error, that is, max_1≤p≤P|η(t _p)| where

$$\displaystyle \begin{aligned} \eta(t)=\frac{t^\beta}{\varGamma(\beta)}\bigg( \sum_{k=1}^K\tilde w_ke^{-\tilde a_kt} -\sum_{l=1}^Lw_{l'}e^{-a_{l'}t}\bigg),\qquad l'=l-M+1, \end{aligned} $$

(21)

and we use a geometric grid in [δ, 1] given by t _p = T ^{(p−1)∕(P−1)}δ ^{(P−p)∕(P−1)} for 1 ≤ p ≤ P with P = 751. The largest reduction consistent with maintaining overall accuracy was when L = 65 and K = 6, and Fig. 4 (Top) plots |η(t)| in this case, as well as the overall relative error (Bottom) for the resulting approximation,

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}\approx\frac{1}{\varGamma(\beta)}\bigg( \sum_{k=1}^K\tilde w_ke^{-\tilde a_kt}+ \sum_{n=L-M}^N w_ne^{-a_nt}\bigg) \quad \text{for }10^{-6}\le t\le10. \end{aligned} $$

(22)

In this way, the number of terms in the exponential sum approximation was reduced from M + 1 + N = 102 to (M + K − L) + 1 + N = 43, with the maximum absolute value of the relative error growing only slightly to 1.07 × 10⁻⁸. Figure 4 (Bottom) shows that the relative error is closely approximated by the first term in (15), that is, $\rho ^M_N(t)\approx -2R(h^{-1})\cos \bigl (2\pi h^{-1}\log t-\varPhi (h^{-1}) \bigr )$ for δ ≤ t ≤ T.

Fig. 4

Top: the additional contribution |η(t)| to the relative error from applying Prony’s method in Example 1 with L = 65 and K = 6. Bottom: the overall relative error for the resulting approximation (22) of t ^−β requiring L − K = 59 fewer terms

Table 1 Performance of Prony’s method for different L and K using the parameters of Example 1

4 Approximation Based on the Substitution $p=\exp (x-e^{-x})$

We now consider the alternative exponents and weights given by (12). A different approach is needed for the error analysis, and we define

$$\displaystyle \begin{aligned} \mathbb{I}(f)=\int_{-\infty}^\infty f(x)\,dx \quad \text{and}\quad \mathbb{Q}(f,h)=h\sum_{n=-\infty}^\infty f(nh)\quad \text{for }h>0, \end{aligned}$$

so that $\mathbb {Q}(f,h)$ is an infinite trapezoidal rule approximation to $\mathbb {I}(f)$. Recall the following well-known error bound.

Theorem 3

Let r > 0. Suppose that f(z) is continuous on the closed strip |ℑz|≤ r, analytic on the open strip |ℑz| < r, and satisfies

$$\displaystyle \begin{aligned} \int_{-\infty}^\infty\bigl(|\,f(x+ir)|+|\,f(x-ir)|\bigr)\,dx\le A_r \end{aligned}$$

with

$$\displaystyle \begin{aligned} \int_{-r}^r|\,f(x\pm iy)|\,dy\to0\quad \mathit{\text{as }}|x|\to\infty. \end{aligned}$$

Then, for all h > 0,

$$\displaystyle \begin{aligned} |\mathbb{Q}(f,h)-\mathbb{I}(f)| \le\frac{A_re^{-2\pi r/h}}{1-e^{-2\pi r/h}}. \end{aligned}$$

Proof

See McNamee et al. [6, Theorem 5.2]. □

For t > 0, we define the entire analytic function of z,

$$\displaystyle \begin{aligned} f(z)=\exp\bigl(-\varphi(z,t)\bigr)(1+e^{-z}), \end{aligned} $$

(23)

where φ(z, t) is the analytic continuation of the function defined in (11). In this way, $t^{-\beta }=\mathbb {I}(f)/\varGamma (\beta )$ by (10).

Lemma 1

If 0 < r < π∕2, then the function f defined in (23) satisfies the hypotheses of Theorem 3 with A _r ≤ Ct ^−β for 0 < t ≤ 1, where the constant C > 0 depends only on β and r.

Proof

A short calculation shows that

$$\displaystyle \begin{aligned} \Re\varphi(x\pm iy,t)=t\exp(x-e^{-x}\cos y)\cos{}(y+e^{-x}\sin y) -\beta(x-e^{-x}\cos y), \end{aligned}$$

and that if 0 < 𝜖 < π∕2 − r, then

$$\displaystyle \begin{aligned} 0\le y+e^{-x}\sin y\le\frac{\pi}{2}-\epsilon \quad \text{ for }x\ge x^*=\log\frac{\sin r}{\pi/2-r-\epsilon} \mbox{ and }0\le y\le r. \end{aligned} $$

(24)

Thus, if x ≥ x ^∗ then $\cos {}(r+e^{-x}\sin r)\ge \cos {}(\pi /2-\epsilon )=\sin \epsilon$ so

$$\displaystyle \begin{aligned} \Re\varphi(x\pm ir,t)\ge t\exp(x-e^{-x^*}\cos r)\sin\epsilon -\beta x+\beta e^{-x}\cos r\ge cte^x-\beta x, \end{aligned}$$

where $c=\exp (-e^{-x^*}\cos r)\sin \epsilon >0$. If necessary, we increase x ^∗ so that x ^∗ > 0. Since |1 + e ^−(x±ir)|≤ 1 + e ^−x,

$$\displaystyle \begin{aligned} \int_{x^*}^\infty|\,f(x\pm ir)|\,dx &=\int_{x^*}^\infty\exp\bigl(-\Re\varphi(x\pm ir,t)\bigr) \bigl|1+e^{-(x\pm ir)}\bigr|\,dx\\ &\le\int_{x^*}^\infty\exp(-cte^x+\beta x)(1+e^{-x})\,dx, \end{aligned} $$

and the substitution p = e ^x then yields, with $p^*=e^{x^*}$,

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \int_{x^*}^\infty|\,f(x\pm ir)|\,dx \le\int_{p^*}^\infty e^{-ctp}p^\beta(1+p^{-1})\,\frac{dp}{p} \le\bigl(1+(p^*)^{-1}\bigr)\int_{p^*}^\infty e^{-ctp}p^\beta\,\frac{dp}{p}\\ &\displaystyle &\displaystyle \qquad \qquad =\frac{1+(p^*)^{-1}}{(ct)^\beta}\int_{ctp^*}^\infty e^{-p}p^\beta \,\frac{dp}{p} \le\frac{1+(p^*)^{-1}}{(ct)^\beta}\int_0^\infty e^{-p}p^\beta \,\frac{dp}{p}\equiv Ct^{-\beta}. \end{array} \end{aligned} $$

Also, if x ≥ 0 then

$$\displaystyle \begin{aligned} \Re\varphi(x\pm ir,t)\ge-t\exp(x-e^{-x}\cos r)-\beta(x-e^{-x}\cos r) \ge-te^x-\beta x \end{aligned}$$

so

$$\displaystyle \begin{aligned} \int_0^{x^*}|\,f(x\pm ir)|\,dx \le\int_0^{x^*}\exp(te^x+\beta x)(1+e^{-x})\,dx \le2x^*\exp\bigl(te^{x^*}+\beta x^*\bigr), \end{aligned}$$

which is bounded for 0 < t ≤ 1. Similarly, if x ≤ 0 then $\exp (x-e^{-x}\cos r)\le 1$ so $\Re \varphi (x\pm ir,t)\ge -t+\beta e^{-x}\cos r$ and therefore, using again the substitution p = e ^x,

$$\displaystyle \begin{aligned} \int_{-\infty}^0|\,f(x\pm ir)|\,dx &\le\int_{-\infty}^0\exp(t-\beta e^{-x}\cos r)(1+e^{-x})\,dx\\ &=\int_0^\infty\exp(t-\beta e^x\cos r)(1+e^x)\,dx =e^t\int_1^\infty e^{-\beta p\cos r}(1+p)\,\frac{dp}{p}, \end{aligned} $$

which is also bounded for 0 < t ≤ 1. The required estimate for A _r follows.

If x ≥ x ^∗, then the preceding inequalities based on (24) show that

$$\displaystyle \begin{aligned} \int_{-r}^r|\,f(x+iy)|\,dy \le2r\max_{|\,y|\le r}|\,f(x+iy)| \le2r\exp(-cte^x+\beta x)(1+e^{-x}), \end{aligned}$$

which tends to zero as x →∞ for any t > 0. Similarly, if x ≤ 0, then $\Re \varphi (x\pm iy)\ge -t+\beta e^{-x}\cos r$ for | y|≤ r, so

$$\displaystyle \begin{aligned} \int_{-r}^r|\,f(x+iy)|\,dy\le2r\exp(t-\beta e^{-x}\cos r)(1+e^{-x}), \end{aligned}$$

which again tends to zero as x →−∞. □

Together, Theorem 3 and Lemma 1 imply the following bound for the relative error (8) in the infinite exponential sum approximation (6).

Theorem 4

Let h > 0 and define a _n and w _n by (12). If 0 < r < π∕2, then there exists a constant C ₁ (depending on β and r) such that

$$\displaystyle \begin{aligned} |\rho(t)|\le C_1 e^{-2\pi r/h}\quad \mathit{\text{for }}0<t\le1. \end{aligned}$$

Proof

The definitions above mean that $hf(nh)=w_ne^{-a_nt}$. □

Thus, a relative accuracy 𝜖 is achieved by choosing h of order $1/\log \epsilon ^{-1}$. Of course, in practice we must compute a finite sum, and the next lemma estimates the two parts of the associated truncation error.

Lemma 2

Let h > 0, 0 < θ < 1 and 0 < t ≤ 1. Then the function f defined in (23) satisfies

$$\displaystyle \begin{aligned} \begin{array}{rcl}{} \frac{h}{\varGamma(\beta)}\sum_{M=-\infty}^{-M-1}f(nh) \le C_2\exp(-\beta e^{Mh})\quad \mathit{\text{for}}\quad Mh\ge\begin{cases}\log(\beta^{-1}-1),&\displaystyle 0<\beta<1/2,\\ 0,&\displaystyle \beta\ge1/2, \end{cases}\\ \end{array} \end{aligned} $$

(25)

and

$$\displaystyle \begin{aligned} \frac{h}{\varGamma(\beta)}\sum_{n=N+1}^\infty f(nh) \le\frac{C_3}{t^\beta}\,\exp\bigl(-\theta te^{Nh-1}\bigr) \quad \mathit{\text{for}}\quad Nh\ge1+\log(\beta t^{-1}). \end{aligned} $$

(26)

When 0 < β ≤ 1, the second estimate holds also with θ = 1.

Proof

If n ≤ 0, then φ(nh, t) ≥−t + βe ^−nh so

$$\displaystyle \begin{aligned}f(nh)\le g_1(-nh)\quad \text{where}\quad g_1(x)=\exp(t-\beta e^x)(1+e^x). \end{aligned}$$

The function g ₁(x) decreases for $x>\log (\beta ^{-1}-1)$ if 0 < β < 1∕2, and for all x ≥ 0 if β ≥ 1∕2, so

$$\displaystyle \begin{aligned} h\sum_{n=-\infty}^{-M-1}f(nh)\le h\sum_{n=M+1}^\infty g_1(nh) \le\int_{Mh}^\infty g_1(x)\,dx \quad \text{for }M\mbox{ as in (\ref{eq: Mh}),} \end{aligned}$$

and the substitution p = e ^x gives

$$\displaystyle \begin{aligned} \int_{Mh}^\infty g_1(x)\,dx=\int_{e^{Mh}}^\infty e^{t-\beta p} (1+p)\,\frac{dp}{p} \le2e^t\int_{e^{Mh}}^\infty e^{-\beta p}\,dp =\frac{2e^t}{\beta}\exp(-\beta e^{Mh}), \end{aligned}$$

so the first estimate holds with C ₂ = 2e∕Γ(β + 1).

If n ≥ 0 we have $\varphi (nh,t)\ge t\exp (nh-1)-\beta nh$ and 1 + e ^−nh ≤ 2, so

$$\displaystyle \begin{aligned}f(nh)\le g_2(nh)\quad \text{where}\quad g_2(x)=2\exp(-te^{x-1}+\beta x). \end{aligned}$$

The function g ₂(x) decreases for $x>1+\log (\beta t^{-1})$, so

$$\displaystyle \begin{aligned} h\sum_{n=N+1}^\infty f(nh)\le\int_{Nh}^\infty g_2(x)\,dx \quad \text{for }N\mbox{ as in (\ref{eq: Nh}),} \end{aligned}$$

and the substitution p = e ^x gives

$$\displaystyle \begin{aligned} \int_{Nh}^\infty g_2(x)\,dx \le 2\int_{e^{Nh}}^\infty e^{-te^{-1}p}p^\beta\,\frac{dp}{p} =2\bigg(\frac{e}{t}\bigg)^\beta \int_{te^{Nh-1}}^\infty e^{-p}p^{\beta-1}\,dp. \end{aligned}$$

Since te ^Nh−1 ≥ β, if 0 < β ≤ 1 then the integral on the right is bounded above by $\beta ^{\beta -1}\exp (-te^{Nh-1})$. If β > 1, then p ^β−1e ^−(1−θ)p is bounded for p > 0 so

$$\displaystyle \begin{aligned} \int_{te^{Nh-1}}^\infty e^{-p}p^{\beta-1}\,dp =\int_{te^{Nh-1}}^\infty e^{-\theta p} (p^{\beta-1}e^{-(1-\theta)p})\,dp\le C\exp(-\theta te^{Nh-1}), \end{aligned}$$

completing the proof. □

It is now a simple matter to see that the number of terms L = M + 1 + N needed to ensure a relative accuracy 𝜖 for δ ≤ t ≤ 1 is of order $(\log \epsilon ^{-1})\log (\delta ^{-1}\log \epsilon ^{-1})$.

Theorem 5

Let a _n and w _n be defined by (12). For 0 < δ ≤ 1 and for a sufficiently small 𝜖 > 0, if

$$\displaystyle \begin{aligned} \frac{1}{h}\ge\frac{1}{2\pi r}\,\log\frac{3C_1}{\epsilon}, \quad M\ge\frac{1}{h}\,\log\bigg(\frac{1}{\beta}\, \log\frac{3C_2}{\epsilon}\bigg),\quad N\ge1+\frac{1}{h}\,\log\bigg(\frac{1}{\theta\delta}\, \log\frac{3C_3}{\epsilon}\bigg), \end{aligned}$$

then

$$\displaystyle \begin{aligned} |\rho^N_M(t)|\le\epsilon\quad \mathit{\text{for }}\delta\le t\le1. \end{aligned}$$

Proof

The inequalities for h, M and N imply that each of C ₁e ^−2πr∕h, $C_2\exp (-\beta e^{Mh})$ and $C_3\exp (-\theta te^{Nh-1})$ is bounded above by 𝜖t ^−β∕3, so the error estimate is a consequence of Theorem 4, Lemma 2 and the triangle inequality. Note that the restrictions on M and N in (25) and (26) will be satisfied for 𝜖 sufficiently small. □

Although the error bounds above require t ∈ [δ, 1], a simple rescaling allows us to treat a general compact subinterval [δ, T]. If $\check a_n=a_n/T$ and $\check w_n=w_n/T^\beta$, then

$$\displaystyle \begin{aligned} \frac{1}{t^\beta}=\frac{1}{T^\beta}\,\frac{1}{(t/T)^\beta} \approx\frac{1}{\varGamma(\beta)} \sum_{n=-M}^N\check w_ne^{-\check a_nt} \end{aligned}$$

for δ ≤ t∕T ≤ 1, or in other words for δ ⋅ T ≤ t ≤ T. Moreover, the relative error $\check \rho ^N_M(t)=\rho ^N_M(t/T)$ is unchanged by the rescaling.

Example 2

We took the same values for β, δ, T, 𝜖, 𝜖 _RD and 𝜖 _RT as in Example 1. Since the constant C ₁ of Theorem 4 is difficult to estimate, we again used (16) to choose h = 0.47962. Likewise, the constant C ₃ in Lemma 2 is difficult to estimate, so we chose N = ⌈h ⁻¹x _δ∕T⌉ = 40. However, knowing C ₂ = 2e∕Γ(β + 1) we easily determined that $C_2\exp (-\beta e^{Mh})\le \epsilon _{\text{RT}}$ for M = 8. The exponents and weights (12) were computed for the interval [δ∕T, 1], and then rescaled as above to create an approximation for the interval [δ, T] with M + 1 + N = 49 terms and a relative error whose magnitude is at worst 2.2 × 10⁻⁸.

The behaviour of the relative error $\rho ^N_M(t)$, shown in Fig. 5, suggests a modified strategy: construct the approximation for [δ, 10T] but use it only on [δ, T]. We found that doing so required N = 45, that is, 5 additional terms, but resulted in a nearly uniform amplitude for the relative error of about 0.97 × 10⁻⁸. Finally, after applying Prony’s method with L = 17 and K = 6 we were able to reduce the number of terms from M + 1 + N = 54 to 43 without increasing the relative error.

Fig. 5

The relative error for the initial approximation from Example 2

To compare these results with those of Li [5], let 0 < α < 1 and let k(t) = t ^α−1∕Γ(α) denote the kernel for the fractional integral of order α. Taking β = 1 − α we compute the weights w _l and exponents a _l as above and define

$$\displaystyle \begin{aligned} k_M^N(t)=\frac{1}{\varGamma(\alpha)\varGamma(1-\alpha)}\sum_{n=-M}^N w_ne^{-a_nt}\quad \text{for }\delta\le t\le T. \end{aligned}$$

The fast algorithm evaluates

$$\displaystyle \begin{aligned} (\mathbb{K}_M^NU)^n=\int_0^{t_{n-1}} k^N_M(t-s)\tilde U(s)\,ds +\int_{t_{n-1}}^{t_n}k(t_n-s)\tilde U(s)\,ds \end{aligned}$$

and our bound $|\rho ^N_M(t)|\le \epsilon$ implies that $|k_M^N(t)-k(t)|\le \epsilon t^{\alpha -1}/\varGamma (\alpha )$ for δ ≤ t ≤ T, so

$$\displaystyle \begin{aligned} \bigl|(\mathbb{K}_M^NU)^n-(\mathbb{K}\tilde U)(t_n)\bigr| \le\epsilon\int_0^{t_{n-1}} \frac{(t_n-s)^{\alpha-1}}{\varGamma(\alpha)}\,|\tilde U(s)|\,ds \le\frac{\epsilon t_n^\alpha}{\varGamma(\alpha+1)}\, \max_{1\le j\le n}|U^j|, \end{aligned}$$

provided Δt _n ≥ δ and t _n ≤ T. Similarly, the method of Li yields $(\mathbb {K}_QU)^n$ but with a bound for the absolute error in (14), so that |k _Q(t) − k(t)|≤ 𝜖′ for δ′≤ t < ∞. Thus,

$$\displaystyle \begin{aligned} \bigl|(\mathbb{K}_QU)^n-(\mathbb{K}\tilde U)(t_n)\bigr| \le\epsilon'\,\frac{\sin\pi\alpha}{\pi}\int_0^{t_{n-1}} \,|\tilde U(s)|\,ds \le\epsilon't_n\,\frac{\sin\pi\alpha}{\pi}\, \max_{1\le j\le n}|U^j|, \end{aligned}$$

provided Δt _n ≥ δ. Li [5, Fig. 3 (d)] required about Q = 250 points to achieve an (absolute) error 𝜖′≤ 10⁻⁶ for t ≥ δ′ = 10⁻⁴ when α = 1∕4 (corresponding to β = 1 − α = 3∕4). In Examples 1 and 2, our methods give a smaller error 𝜖 ≤ 10⁻⁸ using only M + 1 + N = 43 terms with a less restrictive lower bound for the time step, δ = 10⁻⁶. Against these advantages, the method of Li permits arbitrarily large t _n.

5 Conclusion

Comparing Examples 1 and 2, we see that, for comparable accuracy, the approximation based on the second substitution results in far fewer terms because we are able to use a much smaller choice of M. However, after applying Prony’s method both approximations are about equally efficient. If Prony’s method is not used, then the second approximation is clearly superior. Another consideration is that the first approximation has more explicit error bounds so we can, a priori, more easily determine suitable choices of h, M and N to achieve a desired accuracy.