%==============================================================================
\documentclass[11pt,a4paper,twoside]{scrartcl}
%==============================================================================
\usepackage{a4wide}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{theorem}
%\usepackage{showkeys}
%\usepackage{psfig}
%\usepackage{lscape}
\usepackage{color}
%\usepackage{graphics}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage[boxed,Algorithm]{algorithm}
\usepackage{algorithmic}
\usepackage{psfrag}

\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\setcounter{totalnumber}{4}

\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\setcounter{totalnumber}{4}
\newenvironment{tablehere}
  {\def\@captype{table}}
  {}

\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\T}{\ensuremath{\mathbb{T}}}
\renewcommand{\S}{\ensuremath{\mathbb{S}}}
\newcommand{\NZ}{\ensuremath{\mathbb{N}_{0}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Rp}{\ensuremath{\mathbb{R}^{+}}}
\newcommand{\Rn}{\ensuremath{\mathbb{R}^n}}
\newcommand{\Rnn}{\ensuremath{\mathbb{R}^{n \times n}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Pol}{\ensuremath{\Pi}}
\newcommand{\nfft}{\textsf{NFFT}}
\newcommand{\nfftversion}{3.0}

\def\cO{{\cal O}}

\def\veps{\varepsilon}

\def\tT{{\mbox{\tiny{T}}}}
\def\ti{\mbox{\scriptsize{i}}}
\newcommand{\e}{{\,\rm {e}}}
\newcommand{\eim}[1]{{\rm e}^{-2\pi{\ti} #1}}
\newcommand{\eip}[1]{{\rm e}^{ 2\pi{\ti} #1}}
\newcommand{\zb}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\ds}{\displaystyle}
\newcommand{\sinc}{{\rm sinc}}
\newcommand{\dist}{{\rm dist}}
\newcommand{\adj}{{\vdash \hspace*{-1.72mm} \dashv}}

\newcommand{\diag}{{\, \rm diag}}
\renewcommand{\d}{\, \mbox{d}}
\renewcommand{\Box}{\hspace*{0ex} \hfill \rule{1.5ex}{1.5ex} \\}
\newcommand{\bend}{\hspace*{0ex} \hfill \hbox{\vrule height
    1.5ex\vbox{\hrule width 1.4ex \vskip 1.4ex\hrule  width 1.4ex}\vrule
    height 1.5ex}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
%\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}

\newenvironment{Theorem}{\begin{theorem}\sl}{\end{theorem}}
\newenvironment{Lemma}{\begin{lemma}\sl}{\end{lemma}}
\newenvironment{Remark}{\begin{remark}\rm}{\hfill \bend \end{remark}}
%\newenvironment{Algorithm}{\begin{algorithm}\sl}{\hfill \end{algorithm}}
\newenvironment{Example}{\begin{example}\rm}{\hfill \bend \end{example}}
\newenvironment{Corollary}{\begin{corollary}\rm}{\hfill \bend
  \end{corollary}}
\def\invisible#1{\textcolor{white}{#1}}

\numberwithin{equation}{section}
\numberwithin{table}{section}
\numberwithin{figure}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TITLE PAGE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\title{NFFT\nfftversion\ - Summary}
%\author{Jens Keiner
%\thanks{keiner@math.uni-luebeck.de,University of L\"ubeck,
%Institute of  Mathematics, 23560 L\"ubeck}
%\and
%  Stefan Kunis
%\thanks{kunis@mathematik.tu-chemnitz.de, Chemnitz University of Technology,
%Department of Mathematics, 09107 Chemnitz, Germany}
%\and
%  Daniel Potts
%\thanks{potts@mathematik.tu-chemnitz.de, Chemnitz University of Technology,
%Department of Mathematics, 09107 Chemnitz, Germany}
%}
%\date{}
%\maketitle
%\begin{center}
%  \vspace{-8ex}
%  {\large {\tt http://www.tu-chemnitz.de/$\sim$potts/nfft}}
%  \vspace{8ex}
%\end{center}

\title{\vspace{-8ex}\Large NFFT\nfftversion\ - Summary}
\date{}
\author{\large Jens Keiner \and \large Stefan Kunis \and \large Daniel Potts}
\maketitle
\vspace{-8ex}

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'', cf.~\cite{DoSu00}.
The classic algorithm in \cite{CoTu65} computes the discrete
Fourier transform
\begin{equation*}
  f_j= \sum_{k=-\frac{N}{2}}^{\frac{N}{2}-1} \hat{f}_{k} \eim{\frac{kj}{N}}
\end{equation*}
for $j=-\frac{N}{2},\hdots,\frac{N}{2}-1$ and given complex coefficients
$\hat{f}_{k}\in\C$.
Using a divide and conquer approach, the number of floating point operations
is reduced from $\cO(N^2)$ for a straightforward computation to only
$\cO(N\log N)$.
In conjunction with publicly available efficient implementations
\cite{FFTW05}, the fast Fourier transform has become of great importance in
scientific computing.
Its applications include for example digital signal and image processing as
well as the numerical solution of differential and integral equations.
The author of \cite[p. ix]{loan} summarises ``life as we know it
would be very different without the FFT''.

However, two shortcomings of traditional schemes are the need for equispaced
sampling and the restriction to the system of complex exponential functions.
During the last two decades, both problems have attracted much attention.
We refer to \cite{maro96} for an introduction to discrete Fourier analysis
with orthogonal polynomials, spherical harmonics, and more general functions.
The second branch of generalisations dispenses with the need for equispaced
sampling and establishes so-called nonequispaced FFTs, see
e.g. \cite{postta01}.
The common concept in most generalised fast Fourier transforms - and other
algorithms for the computation with dense matrices - is the use of
approximation schemes.
The functions involved, e.g. the complex exponentials, are replaced by
approximations with prescribed accuracy that allow for the design of a fast 
algorithm.
We trade exactness for efficiency; instead of precise computations, the
proposed methods guarantee a given target accuracy.

The principal contribution of the present software package is a publicly
available implementation of various fast algorithms for discrete Fourier
transforms.
For notational convenience let the multi-index set
\begin{equation*}
  I_{\zb N} = \left\{ \zb k=\left(k_t\right)_{t=0,\hdots,d-1} \in \Z^d: -
    \frac{N_t}{2} \le k_t < \frac{N_t}{2} ,\;t=0,\hdots,d-1\right\},
\end{equation*}
with $\zb N=\left(N_t\right)_{t=0,\hdots,d-1}\in 2\N^d$ be given.
For given Fourier coefficients $\hat f_{\zb k} \in \C$, $\zb k \in I_{\zb N}$,
and arbitrary nodes $\zb x_j \in [-1/2,1/2)^d$, $j=0,\hdots,M-1$, we consider
the computation of 
\begin{equation*}
  f\left(\zb x_j\right) = \sum_{\zb k\in I_{\zb N}} \hat{f}_{\zb k} \eim{\zb
    k\zb x_j},\quad  j=0,\hdots,M-1.
\end{equation*}
Obviously, the straightforward algorithm for this task takes $\cO(M|I_{\zb
  N}|)$ floating point operations.
In contrast, the {\em nonequispaced fast Fourier transform} computes the above
sums up to a user-specified accuracy in $\cO(|I_{\zb N}|\log|I_{\zb N}|+M)$
operations.
The implemented routines are state-of-the-art with respect to recently
suggested improvements, see e.g. \cite{GrLe04}, and use the highly efficient
FFTW library \cite{FFTW05}.

The generalisations of the NFFT include fast algorithms for several discrete
Fourier transforms.
Due to its relevance in tomography, geophysics, and meteorology, we would like
to highlight the nonequispaced fast spherical Fourier transform (NFSFT).
In analogy to the complex exponentials $\mathrm{e}^{\mathrm{i} k x}$ on the
torus, the spherical harmonics $Y_k^n$ form the orthogonal Fourier basis with
respect to the usual inner product on the sphere.
For given Fourier coefficients $\hat f_k^n \in \C$ and arbitrary nodes
with longitude $\vartheta_j\in[0,\pi]$ and latitude $\varphi_j\in [0,2\pi)$,
we are interested in the evaluation of
\begin{equation*}
  f\left(\vartheta_j,\varphi_j\right) =
  \sum_{k=0}^N \sum_{n=-k}^k \hat f_k^n
  Y_{k}^n\left(\vartheta_j,\varphi_j\right),\quad  j=0,\hdots,M-1.
\end{equation*}
Here, our implemented scheme reduces the computational costs from $\cO(MN^2)$
operations to only $\cO(N^2\log^2 N+M)$.
Further fast transforms include the Fourier transforms with nonequispaced data
in time and frequency domain, real trigonometric transforms, and sparse FFTs.
All these Fourier transforms come along with their adjoint algorithms, used in
quadrature rules for example, and inverse transforms as used for scattered
data approximation.

The NFFT and its generalisations have found a lot of applications, where the
current release of the library includes various fast summation methods,
reconstruction algorithms in medical imaging, and the polar FFT as part of our
ridgelet transform.
We would like to highlight the fast summation method, because this problem
arises in integral equations or potential theory.
In particular, our method proves comparable with the celebrated fast multipole
method \cite{greenrokh87}.

The documentation of our library is split into two parts:
The tutorial \cite{nfft3_tutorial} surveys the fast Fourier transform at
nonequispaced nodes, its generalisations, and inversion.
Moreover it provides an overview over the C library which allows users to
compute their first transforms by using simple interfaces to the computational
kernels.
The detailed documentation (part of the source tree) of all user functions,
options and parameters is done with Doxygen \cite{doxygen} and allows for
further optimisation with respect to speed, accuracy, and memory usage.

\begin{footnotesize}
\bibliographystyle{abbrv}
\bibliography{../references/references}
\end{footnotesize}

\end{document}