Fast and oblivious convolution quadrature
Please always quote using this URN: urn:nbn:de:0297-zib-8437
- 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.
Author: | Achim Schädle, Maria Lopez-Fernandez, Christian Lubich |
---|---|
Document Type: | ZIB-Report |
Tag: | Runge-Kutta methods; Volterra integral equation; anomalous diffusion; convolution; numerical integration |
MSC-Classification: | 65-XX NUMERICAL ANALYSIS / 65Rxx Integral equations, integral transforms / 65R20 Integral equations |
Date of first Publication: | 2005/01/24 |
Series (Serial Number): | ZIB-Report (05-09) |
ZIB-Reportnumber: | 05-09 |
Published in: | Appeared in:SIAM J. Sci. Comput. Vol. 28(2) (2005) 421-438 |