The principal contribution of this thesis is the further development of computational tools in Fourier analysis that generalise the FFT: 1. We start with a unified introduction to discrete Fourier transforms on the d-dimensional torus, the hyperbolic cross, and the sphere as evaluations of corresponding polynomials at a set of sampling nodes. Furthermore, we follow the“smoothness-and-decay”principle and construct for their subsequent usage sharply localised trigonometric and spherical polynomials from “smooth” Fourier coefficients. 2. Subsequently, fast Fourier transforms are considered. In contrast to [BD89, DH94, PST98b], our FFTs on the sphere and on the hyperbolic cross allow for arbitrary sampling schemes. Moreover, we focus on the substantially different computational costs that arise in various implementations of the nonequispaced fast Fourier transform and improve [DR93, Bey95, AD96, Ste98, PST01] to trade precomputation storage as well as target accuracy for computation time in a manageable way. 3. We contribute new versions of the fast Gauss transform. Compared to multipole approximations in previously suggested schemes [Str91, GS91, GS98, BR02], our method relies solely on nonequispaced FFTs. Uniform error estimates are proven and allow for the adjustment of involved parameters. We easily obtain a matrix formulation and show that the proposed algorithm performs as accurately as the corresponding truncated singular value decomposition but is orders of magnitude faster. 4. The discrete Fourier transform is a unitary operation up to a constant and hence, the inverse is simply given by its scaled adjoint. However, ambiguity arises for nonequispaced sampling nodes where even the number of Fourier coefficients and the number of samples need not coincide. Early approaches for an inversion of the nonequispaced fast Fourier transform suggested to use simply a weighted adjoint NFFT as an approximate inverse, see for example [JMNM91]. In contrast, we provide least squares and interpolation formulations, where the latter are generalised to the sphere and the hyperbolic cross. The convergence of corresponding algorithms is analysed in detail, in particular, we prove rigorous eigenvalue estimates for the involved matrices. Thus, the proposed methods achieve a given target accuracy in a certain number of iterations and hence with proven computational costs.weiterlesen