MiS Preprint Repository

Usually, the fast evaluation of a convolution integral ${\int }_{\mathbb{R}}f(y)g(x-y)\mathrm{d}y$ requires that the functions $f,g$ are discretised on an equidistant grid in order to apply the fast Fourier transform. Here we discuss the efficient performance of the convolution in locally refined grids. More precisely, $f$ and $g$ are assumed to be piecewise linear and the convolution result is projected into the space of linear functions in a given locally refined grid. Under certain conditions, the overall costs are still $\mathcal{O}(N\log N)$, where $N$ is the sum of the dimensions of the subspaces containing $f$, $g$ and the resulting function.