Fast and Exact Projected Convolution of Piecewise Linear Functions on Non-equidistant Grids - Extended Version

Wolfgang Hackbusch

Contact the author: Please use for correspondence this email.
Submission date: 09. Oct. 2006 (revised version: December 2006)
Pages: 22
published in: From nano to space / M. H. Breitner (ed.)
Berlin : Springer, 2008. - P. 145 - 160 
DOI number (of the published article): 10.1007/978-3-540-74238-8_12
Bibtex
with the following different title: Fast projected convolution of piecewise linear functions on non-equidistant grids
MSC-Numbers: 44A35, 42A55
Keywords and phrases: convolution integral
Download full preprint: PDF (262 kB), PS ziped (225 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, 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 , where N is the sum of the dimensions of the subspaces containing f, g and the resulting function.