Nonequispaced Hyperbolic Cross Fast Fourier Transform
|FFT with 2dn
|NHCFFT||cd2nn2d-2(|log ε|d + logdn)|
|LHCFFT||c(M log M + |Hnd|)|
|Table 1:||Computational complexity of different
Fourier transform algorithms
The efficient evaluation of the trigonometric polynomial at the sparse grid nodes xj ∈ Snd, j = 0, …, |Snd| - 1, is called hyperbolic cross fast Fourier transform (HCFFT) and the reconstruction of Fourier coefficients on the hyperbolic cross from samples at the sparse grid nodes inverse HCFFT. Both transforms can be computed in cd2nnd floating point operations.
For arbitrary sampling nodes xj ∈ Td, j = 0, …, M - 1, and M = |Snd|, the naive evaluation of the trigonometric polynomial ƒ is called nonequispaced hyperbolic cross discrete Fourier transform (NHCDFT) and takes cd22nn2d-2 floating point operations. This complexity can be improved to cd2nn2d-2(|log ε|d + logdn) by means of an approximation scheme (NHCFFT) as outlined in the first manuscript below.
To evaluate a multivariate trigonometric polynomial at the nodes xj = jz / M mod 1, j = 0, …, M - 1, z ∈ ℕd, M ∈ ℕ, of a rank-1 lattice one only has to compute a one-dimensional FFT. If the rank-1 lattice allows for the exact reconstruction of the Fourier coefficients from the sample values we call it a nonaliasing lattice. This lattice based hyperbolic cross fast Fourier transform (LHCFFT) is quite simple to implement, in contrast to the HCFFT numerically stable, and takes c(M log M + |Hnd|) floating point operations. Note that the constant here is independent of d.