Fast and Oblivious Convolution Quadrature

Unknown author(s)

SIAM Journal on Scientific Computing · 2006 · 138 citations · 16 references

DOIFull text

Open access

Concepts

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

References

16