doxygen.dox

/*
 * 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
 *  
 */