

Preprint 102/2006
Fast and Exact Projected Convolution for Non-equidistant Grids - Extended Version
Wolfgang Hackbusch
Contact the author: Please use for correspondence this email.
Submission date: 25. Sep. 2006 (revised version: March 2007)
Pages: 42
published in: Computing, 80 (2007) 2, p. 137-168
DOI number (of the published article): 10.1007/s00607-007-0229-z
Bibtex
with the following different title: Fast and exact projected convolution for non-equidistant grids
MSC-Numbers: 44A35, 42A55
Keywords and phrases: convolution integral, non-uniform grids, discrete convolution
Download full preprint: PDF (439 kB), PS ziped (302 kB)
Abstract:
Usually, the fast evaluation of a convolution integral 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, the convolution result is projected into some given locally
refined grid. Under certain conditions, the overall costs are still
where N is the sum of the dimensions of the subspaces containing f, g and the resulting function.