Source-linked AI summary
Fast evaluation of the Caputo fractional derivative and its applications to fractional diffusion equations
Shidong Jiang, Jiwei Zhang, Qian Zhang, Zhimin Zhang
TL;DR
The paper addresses the storage and quadratic work required by long-memory Caputo derivative discretizations. It introduces a sum-of-exponentials history approximation and applies it within fractional diffusion solvers, obtaining nearly optimal complexity while retaining stability and convergence properties.
Problem
Existing Caputo discretizations require storing all previous values and incur O(N_T^2) work, creating a bottleneck for long-time fractional diffusion simulations.
Method
The method splits the Caputo convolution into local and history parts, uses L1 locally, approximates the history kernel by exponentials, and evaluates the resulting convolution recursively.
Results
The resulting algorithms have nearly optimal complexity, with O(N_TN_exp) work and O(N_exp) storage for derivative evaluation and corresponding reductions for fractional diffusion solvers.
Takeaways & Limitations
The scheme provides an efficient and reliable tool for long-time large-scale fractional PDE simulations while preserving the convergence order of standard finite difference schemes.
Takeaways & Limitations
The reported analysis assumes u(t) ∈ C^2[0,t_n] for the stated error result, and extensions to high-order and broader fractional PDE schemes remain future work.
Abstract
from arXiv · showhide
We present an efficient algorithm for the evaluation of the Caputo fractional derivative $_0^C\!D_t^αf(t)$ of order $α\in (0,1)$, which can be expressed as a convolution of $f'(t)$ with the kernel $t^{-α}$. The algorithm is based on an efficient sum-of-exponentials approximation for the kernel $t^{-1-α}$ on the interval $[Δt, T]$ with a uniform absolute error $\varepsilon$, where the number of exponentials $N_{\text{exp}}$ needed is of the order $O\left(\log\frac{1}{\varepsilon}\left( \log\log\frac{1}{\varepsilon}+\log\frac{T}{Δt}\right) +\log\frac{1}{Δt}\left( \log\log\frac{1}{\varepsilon}+\log\frac{1}{Δt}\right) \right)$. As compared with the direct method, the resulting algorithm reduces the storage requirement from $O(N_T)$ to $O(N_{\text{exp}})$ and the overall computational cost from $O(N_T^2)$ to $O(N_TN_{\text{exp}})$ with $N_T$ the total number of time steps. Furthermore, when the fast evaluation scheme of the Caputo derivative is applied to solve the fractional diffusion equations, the resulting algorithm requires only $O(N_SN_{\text{exp}})$ storage and $O(N_SN_TN_{\text{exp}})$ work with $N_S$ the total number of points in space; whereas the direct methods require $O(N_SN_T$) storage and $O(N_SN_T^2)$ work. The complexity of both algorithms is nearly optimal since $N_{\text{exp}}$ is of the order $O(\log N_T)$ for $T\gg 1$ or $O(\log^2N_T)$ for $T\approx 1$ for fixed accuracy $\varepsilon$. We also present a detailed stability and error analysis of the new scheme for solving linear fractional diffusion equations. The performance of the new algorithm is illustrated via several numerical examples. Finally, the algorithm can be parallelized in a straightforward manner.
1. Introduction.
The paper targets the long-memory cost of Caputo fractional-derivative evaluation and introduces a sum-of-exponentials history approximation. Applied to fractional diffusion equations, the scheme preserves stability and convergence while reducing computational and storage complexity.
- Motivation: Existing L1 and higher-order discretizations require all previous function values, yielding O(N_T) average storage and O(N_T^2) total work.This creates a bottleneck for long-time simulations, especially for fractional partial differential equations.
- Fast evaluation: The proposed Caputo scheme splits the convolution into a local part handled by L1 approximation and a history part approximated using the kernel t^-1-α.Integration by parts converts the history contribution into a convolution involving t^-1-α.
- Fractional diffusion applications: For fractional diffusion equations, the resulting algorithm uses O(N_SN_TN_exp) work and O(N_SN_exp) storage instead of the direct method’s quadratic-in-time costs.The fast evaluation is incorporated into existing finite difference schemes for linear and nonlinear equations.
- Analysis and validation: The paper provides stability and error analyses and reports that the diffusion scheme has the same order of convergence as standard finite difference schemes.The scheme is stated to be unconditionally stable with respect to arbitrary step sizes.
2. Fast Evaluation of the Caputo Fractional Derivative.
The fast Caputo evaluator separates local and history contributions, approximates the history kernel by exponentials, and updates each exponential recursively. This yields nearly optimal work and storage while addressing numerical implementation issues such as cancellation and stiffness.
- Algorithm construction: The Caputo convolution is split into a local interval [t_n-1,t_n] and a history interval [0,t_n-1].The local part uses the standard L1 approximation, while integration by parts removes u′ from the history part.
- Kernel approximation: The history kernel t^-1-α is approximated on [Δt,T] by a sum of exponentials with uniform absolute error ε.The construction uses an integral representation, truncation, dyadic intervals, and Gaussian quadrature.
- Kernel approximation: For 1 < β < 2, the approximation is constructed from Gauss-Jacobi quadrature on an end interval and Gauss-Legendre quadrature on dyadic intervals.The theorem gives a constructive approximation with an explicit error bound and the stated N_exp complexity.
- Complexity comparison: The construction’s total exponential count is given by formula (1.2), while prior approaches provide related approximations under different error and interval settings.The paper identifies the structure of its bound as a distinguishing feature relative to the cited theoretical results.
- Numerical exponential counts: Reduction methods can lower the unnecessarily large constructive exponential count, and Table 2.1 reports actual counts for different ε and T/Δt values.The table fixes Δt = 10^-3 and uses ε as its first-column parameter.
- History evaluation: A recurrence updates each exponential with O(1) work per time step, reducing total work from O(N_T^2) to O(N_TN_exp) and memory from O(N_T) to O(N_exp).The history state at the previous time step is reused.
- Implementation: Linear interpolation can evaluate the recurrence integral analytically, but small s_iΔt may cause cancellation in the resulting weights.A short Taylor expansion of exponentials is recommended in that regime.
- Implementation: Evaluating exponential convolutions through an equivalent ODE system may impose very small time steps because the resulting system is stiff.The paper therefore prefers direct recurrence evaluation for this setting.
3. Application I: Linear Fractional Diffusion Equation.
The fast Caputo-derivative evaluation is incorporated into a finite difference scheme for linear fractional diffusion equations. The resulting scheme is unconditionally stable, retains the direct method’s convergence orders, and substantially reduces computational cost for increasing time-step counts.
- Construction of the New Finite Difference Scheme: The fast scheme replaces the standard L1 approximation in the existing finite difference method for the linear fractional diffusion problem.It uses the fast Caputo-derivative evaluation within the finite difference framework.
- Stability and Error Analysis of the New Scheme: The scheme is unconditionally stable for arbitrary step sizes with compactly supported initial data and source terms.This stability result is stated for the finite difference scheme applied to the linear fractional diffusion problem.
- Stability and Error Analysis of the New Scheme: The truncation error is bounded by c1(∆t^(2−α) + h^2 + ε) at interior points.The bound combines temporal discretization, spatial discretization, and sum-of-exponentials approximation errors.
- Numerical Results: The fast and direct schemes both achieve temporal convergence order O(∆t^(2−α)) and spatial convergence order O(h^2).The reported convergence orders are given for α = 0.2 and α = 0.5 in the numerical tests.
- Numerical Results: The direct scheme scales like O(NT^2), whereas CPU time for the fast scheme increases almost linearly with NT and is significantly lower even for modest NT.The comparison is shown for Application I with NS = 30 and α = 0.5.
4. Application II: Nonlinear Fractional Diffusion Equation.
The paper applies its fast Caputo-derivative evaluation within finite-difference schemes for nonlinear fractional diffusion equations, using Fisher and Huxley examples to assess convergence and computational performance.
- Nonlinear models: The nonlinear problem is tested through fractional Fisher and Huxley equations with specified reaction terms and double-Gaussian initial data.The Fisher and Huxley models represent applications in biological and physical settings.
- Numerical scheme: The finite-difference scheme uses the L1 approximation to discretize the Caputo derivative and incorporates the fast evaluation method.The paper presents the resulting fast scheme for solving the nonlinear diffusion problem.
- Convergence: The Fisher and Huxley experiments report the same convergence order O(h^2 + ∆t) in L∞ norm as the direct scheme.This result is reported for α = 0.2 and α = 0.5 in both examples.
- Performance: The fast scheme takes much less computational time than the direct scheme in both nonlinear examples.The experiments separately report this outcome for the Fisher and Huxley equations.
- Performance: The CPU-time plot shows almost linear complexity in the total number of time steps for the fast scheme.The comparison is made against the direct scheme for the Fisher and Huxley equations.
5. Conclusions.
The paper concludes with a fast Caputo-derivative algorithm based on sum-of-exponentials approximation and applies it to fractional diffusion equations. The resulting schemes retain standard convergence orders while achieving nearly optimal computational complexity and storage.
- Conclusions: The algorithm evaluates the Caputo fractional derivative for 0 < α < 1 using a sum-of-exponentials approximation of the kernel t^-1-α.The approximation has absolute error ε over [∆t, T].
- Conclusions: The number of exponentials has an explicitly analyzed order depending on ε, ∆t, and T.The supplied passage states the order expression but does not preserve its complete displayed formula.
- Conclusions: The fast algorithm has nearly optimal CPU-time and storage complexity.Its recurrence-based convolution evaluation removes the direct method's quadratic-in-time bottleneck.
- Conclusions: Numerical results for linear and nonlinear fractional diffusion equations show the new scheme has the same convergence order as standard finite-difference schemes.The same results also report nearly optimal CPU-time and storage complexity.
- Extensions: Future work includes high-order fractional-derivative schemes, fractional PDEs with time- and space-fractional derivatives, and high-dimensional artificial boundary conditions.These extensions are described as ongoing investigations.
Appendix A. The Proof of Lemma 2.8.
The appendix derives estimates used in Lemma 2.8 by applying inequalities, coefficient formulas, and substitutions to intermediate bounds.
- Proof: The proof begins by applying the fast evaluation scheme definition and the Cauchy-Schwarz inequality.
- Proof: The argument combines intermediate estimates and sums an inequality from k = 1 to n.These steps lead toward the stated lemma.