Fast and oblivious convolution quadrature

Abstract

We give an algorithm to compute $N$ steps of a convolution quadrature approximation to a continuous temporal convolution using only $O(N\log N)$ multiplications and $O(\log N)$ active memory. The method does not require evaluations of the convolution kernel, but instead $O(\log N)$ evaluations of its Laplace transform, which is assumed sectorial. The algorithm can be used for the stable numerical solution with quasi-optimal complexity of linear and nonlinear integral and integro-differential equations of convolution type. In a numerical example we apply it to solve a subdiffusion equation with transparent boundary conditions.

References in corpus (1)

• Fast Runge-Kutta approximation of inhomogeneous parabolic equations

Cited by in corpus (19)

• Superconvergence of a discontinuous Galerkin method for fractional diffusion and wave equations
• A spectral order method for inverting sectorial Laplace transforms
• Efficient computation of the Grunwald-Letnikov fractional diffusion derivative using adaptive time step memory
• Fast summation by interval clustering for an evolution equation with memory
• Fast Runge-Kutta approximation of inhomogeneous parabolic equations
• A Gauss-Jacobi Kernel Compression Scheme for Fractional Differential Equations
• A fast time domain solver for the equilibrium Dyson equation
• Fast algorithms for convolution quadrature of Riemann-Liouville fractional derivative
• A spectrally accurate step-by-step method for the numerical solution of fractional differential equations
• Boundary-Finite Element discretization of time dependent acoustic scattering by elastic obstacles with piezoelectric behavior
• A high-order integral equation-based solver for the time-dependent Schrodinger equation
• A linear Galerkin numerical method for a quasilinear subdiffusion equation
• Shock-driven nucleation and self-organization of dislocations in the dynamical Peierls model
• A fast, high-order numerical method for the simulation of single-excitation states in quantum optics
• Convolution quadrature methods for time-domain scattering from unbounded penetrable interfaces
• Statistics of non-linear stochastic dynamical systems under Lévy noises by a convolution quadrature approach
• Eliminating artificial boundary conditions in time-dependent density functional theory using Fourier contour deformation
• Analysis and implementation of collocation methods for fractional differential equations
• Grünwald--Letnikov Memory Truncation in a Fractional Duffing Oscillator: Coherence Loss and Effective Delay Complexity