Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids

Abstract:

We propose a fast discrete Fourier transform for a given data set which may be generated from sampling a function of $d$-variables on a sparse grid and a fast discrete backward Fourier transform on a hyperbolic cross index set. Computation of these transforms can be formulated as evaluation of dimension-reducible sums on sparse grids. We introduce a fast algorithm for evaluating such sums and prove that the total number of operations needed in the algorithm is $\mathcal {O}(n\log ^{d}n)$, where $n$ is the number of components along each coordinate direction of the data set. We then use it to develop fast algorithms for computing the discrete Fourier transform on the sparse grid and the discrete backward Fourier transform on the hyperbolic cross index set. We also show that if the given data set is sampled from a function having regularity of order $s$, then its discrete Fourier transform has the optimal approximation order $\mathcal {O}(n^{-s})$. Numerical examples are presented to demonstrate the approximation accuracy and computational efficiency of the proposed algorithms.