We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
110/2006
Fast and Exact Projected Convolution of Piecewise Linear Functions on Non-equidistant Grids - Extended Version
Wolfgang Hackbusch
Abstract
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.
