Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

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.

Received:
Oct 9, 2006
Published:
Oct 9, 2006
MSC Codes:
44A35, 42A55
Keywords:
convolution integral

Related publications

inBook
2008 Repository Open Access
Wolfgang Hackbusch

Fast projected convolution of piecewise linear functions on non-equidistant grids

In: From nano to space / Michael H. Breitner (ed.)
Berlin : Springer, 2008. - pp. 145-160