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$ have a simple structure based on an equidistant grid in order to apply the fast Fourier transform. Here we discuss the efficient performance of the convolution of $hp$-functions in certain locally refined grids. More precisely, the convolution result is projected into some given $hp$-space (Galerkin approximation). The overall cost is $\mathcal{O}(p^{2}N\log N),$ where $N$ is the sum of the dimensions of the subspaces containing $f$, $g$ and the resulting function, while $p$ is the maximal polynomial degree.