Fast and Oblivious Convolution Quadrature

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 uses 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.