Fast discrete fourier transform on generalized sparse grids

In this paper, we present an algorithm for trigonometric interpolation of multivariate functions on generalized sparse grids and study its application for the approximation of functions in periodic Sobolev spaces of dominating mixed smoothness. In particular, we derive estimates for the error and the cost. We construct interpolants with a computational cost complexity which is substantially lower than for the standard full grid case. The associated generalized sparse grid interpolants have the same approximation order as the standard full grid interpolants, provided that certain additional regularity assumptions on the considered functions are fulfilled. Numerical results validate our theoretical findings