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.