Fast summation by interval clustering for an evolution equation with memory

Abstract

We solve a fractional diffusion equation using a piecewise-constant, discontinuous Galerkin method in time combined with a continuous, piecewise-linear finite element method in space. If there are $N$ time levels and $M$ spatial degrees of freedom, then a direct implementation of this method requires $O(N^{2}M)$ operations and $O(NM)$ active memory locations, owing to the presence of a memory term: at each time step, the discrete evolution equation involves a sum over \emph{all} previous time levels. We show how the computational cost can be reduced to $O(MN\log N)$ operations and $O(M\log N)$ active memory locations.

28 pages, 1 figure

References in corpus (1)

• Fast and oblivious convolution quadrature

Cited by in corpus (17)

• Superconvergence of a discontinuous Galerkin method for fractional diffusion and wave equations
• Unconditional convergence of a fast two-level linearized algorithm for semilinear subdiffusion equations
• Existence, uniqueness and regularity of the solution of the time-fractional Fokker-Planck equation with general forcing
• Exponential sum approximations for $t^{-\beta }$
• A parallel-in-time two-sided preconditioning for all-at-once system from a non-local evolutionary equation with weakly singular kernel
• A posteriori error analysis for approximations of time-fractional subdiffusion problems
• A hybridized discontinuous Galerkin method for 2D fractional convection-diffusion equations
• Fast evaluation of the Caputo fractional derivative and its applications to fractional diffusion equations
• An Analysis of Galerkin Proper Orthogonal Decomposition for Subdiffusion
• A stable fast time-stepping method for fractional integral and derivative operators
• A new class of semi-implicit methods with linear complexity for nonlinear fractional differential equations
• High order fast algorithm for the Caputo fractional derivative
• Time-stepping discontinuous Galerkin methods for fractional diffusion problems
• An accurate spectral method for Maxwell equations in Cole-Cole dispersive media
• Uniform stability for a spatially-discrete, subdiffusive Fokker-Planck equation
• A discontinuous Galerkin method for time fractional diffusion equations with variable coefficients
• Multiresolution Galerkin method for solving the functional distribution of anomalous diffusion described by time-space fractional diffusion equation