/* * Copyright (c) 2002, 2017 Jens Keiner, Stefan Kunis, Daniel Potts * * This program is free software; you can redistribute it and/or modify it under * the terms of the GNU General Public License as published by the Free Software * Foundation; either version 2 of the License, or (at your option) any later * version. * * This program is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more * details. * * You should have received a copy of the GNU General Public License along with * this program; if not, write to the Free Software Foundation, Inc., 51 * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ /** * \mainpage notitle * * \section introduction Introduction * * Fast Fourier transforms (FFTs) belong to the '10 algorithms with the * greatest influence on the development and practice of science and * engineering in the 20th century'. * The classic algorithm computes the discrete Fourier transform * \f[ * f_j= \sum_{k=-\frac{N}{2}}^{\frac{N}{2}-1} \hat{f}_{k} * {\rm e}^{-2\pi{\rm i}\frac{kj}{N}} * \f] * for \f$j=-\frac{N}{2},\dots,\frac{N}{2}-1\f$ and given complex * coefficients \f$\hat{f}_{k}\in\mathbb{C}\f$. * Using a divide and conquer approach, the number of floating point * operations is reduced from \f${\cal O}(N^2)\f$ for a straightforward * computation to only \f${\cal O}(N\log N)\f$. * In conjunction with publicly available efficient implementations the fast * Fourier transform has become of great importance in scientific computing. * * However, two shortcomings of traditional schemes are the need for * equispaced sampling and the restriction to the system of complex * exponential functions. * The NFFT is a C subroutine library for computing the nonequispaced discrete * Fourier transform (NDFT) and its generalisations in one or more dimensions, * of arbitrary input size, and of complex data. * * More precisely, we collect the possible frequencies * \f$\mathbf{k}\in\mathbb{Z}^d\f$ in the multi-index set * \f[ * I_{\mathbf{N}} := \left\{ \mathbf{k}=\left(k_t\right)_{t=0,\dots,d-1} * \in \mathbb{Z}^d: - * \frac{N_t}{2} \le k_t < \frac{N_t}{2} ,\;t=0,\dots,d-1\right\}, * \f] * where \f$\mathbf{N}=\left(N_t\right)_{t=0,\dots,d-1}\f$ is the * multibandlimit, i.e., \f$N_t\in 2\mathbb{N}\f$. * For a finite number of given Fourier coefficients * \f$\hat f_{\mathbf{k}} \in \mathbb{C}\f$, * \f$\mathbf{k}\in I_{\mathbf{N}}\f$, we consider the * fast evaluation of the trigonometric polynomial * \f[ * f\left(\mathbf{x}\right) * := \sum_{ \mathbf{k}\in I_{ N}} \hat{f}_{\mathbf{ k}} * {\rm e}^{-2\pi{\rm i}\mathbf{k}\mathbf{ x}} * \f] * at given nonequispaced nodes \f$\mathbf{x}_j \in \mathbb{T}^d\f$, * \f$j=0,\ldots, M-1\f$, from the * \f$ d\f$-dimensional torus as well as the * adjoint problem, the fast evaluation of sums of the form * \f[ * \hat h_{\mathbf{k}} := \sum_{j=0}^{M-1} {f}_{j} * {\rm e}^{2\pi{\rm i}\mathbf{k}\mathbf{ x}_j}. * \f] * * \subsection generalisations Generalisations * * The generalisations of the NFFT include * - NNFFT - nonequispaced in time and frequency fast Fourier transform, * - NFCT/NFST - nonequispaced fast (co)sine transform, * - NSFFT - nonequispaced sparse fast Fourier transform, * - FPT - fast polynomial transform, * - NFSFT - nonequispaced fast spherical Fourier transform. * * Furthermore, we consider the inversion of the above transforms by * iterative methods. * * \section faq FAQ - Frequently Asked Questions * * * see https://www.tu-chemnitz.de/~potts/nfft/faq.php * */