%==============================================================================
\documentclass[11pt,a4paper,twoside,bibtotoc]{scrartcl}
%==============================================================================

% LaTeX packages
\usepackage{a4wide}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{theorem}
\usepackage{color}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage[boxed,Algorithm]{algorithm}
\usepackage{algorithmic}
\usepackage{multicol}
%\usepackage{showkeys}

% Allow for more figures on each side
\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\setcounter{totalnumber}{4}

% Shortcuts for maths symbols.
\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{\nfft}{\textsf{NFFT}}
\newcommand{\cO}{\ensuremath{\mathcal{O}}}
\newcommand{\tT}{\ensuremath{\text{\tiny{T}}}}
\newcommand{\ti}{\ensuremath{\text{\scriptsize{i}}}}
\newcommand{\e}{{\ensuremath{\mathrm{e}}}}
\newcommand{\eim}[1]{\ensuremath{\mathrm{e}^{-2\pi{\ti} #1}}}
\newcommand{\eip}[1]{\ensuremath{\mathrm{e}^{ 2\pi{\ti} #1}}}
\renewcommand{\mathbf}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\ds}{\displaystyle}
\newcommand{\sinc}{{\rm sinc}}
\newcommand{\dist}{{\rm dist}}
\newcommand{\adj}{{\vdash \hspace*{-1.72mm} \dashv}}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\dd}{d}
\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}
}

\def\invisible#1{\textcolor{white}{#1}}

% Environment Numbering
\numberwithin{equation}{section}
\numberwithin{table}{section}
\numberwithin{figure}{section}

%===============================================================================
% Title Page
%===============================================================================
\begin{document}
\begin{center}
Answer to the Referee Report\\[2ex]
{\Large
``Using NFFT 3 -- a software library for various \\ nonequispaced fast
  Fourier transforms'' }\\[2ex]
by Jens Keiner, Stefan Kunis, and Daniel Potts
\end{center}
%===============================================================================

First of all, we thank all three referees for their helpful comments and valuable
suggestions.

\section*{Referee 3}
\label{sect:1}

\begin{itemize}
  \item
    \begin{quote}
      Referee:
      The authors may consider to follow or mention the other commonly
      recognized names, such as USFFT by many mathematicians
      and NUFFT by engineers.
    \end{quote}
    %We now mention the alternative abbreviations USFFT and NUFFT on the first
    %Ppage of the paper.
    References and the alternative abbreviations USFFT and NUFFT are contained
    in the Appendix ``Further NFFT approaches'' (now A.4).
  \item
    \begin{quote}
      Referee:
      This package does not take arbitrary sample nodes as it claims.
      The samples are required to be on a Kronecker grid, which
      may be non-equally spaced in each and every dimension involved.
    \end{quote}
    The software library \emph{does} take arbitrary sample nodes. We do not
    require samples to be on a Kronecker grid or anything similar.
  \item
    \begin{quote}
      Referee:
      The package limits the data structure to linearized arrays,
      which entails additional code and time for data re-formatting
      for high-dimensional NUFFTs.
    \end{quote}
    Data structures are linear and we do not see this as a
    substantial limitation. Like FFTW, we expect multi-dimensional data to be
    stored as a consecutive block in row-major order ('C order').
    Fixed-size arrays allocated by the user are amenable to convenient multiple
    applications of the \verb"[]" operator, e.g. \verb"a[2][4][1]", but the use
    of such arrays cannot  recommended in general (e.g., they are allocated on
    the stack). For dynamic arrays, the linear index has to be computed.

    Additionally, for nonequispaced transforms, nodes can be
    completely unstructured and multi-dimensional structures, like grids,
    are special cases. Most often, nodes will not be aligned
    and the most appropriate data structure for such nodes is, without further
    assumptions, a linear array.

    A current limitation is that (for now) we do not support strided
    data (i.e., general FFTW-style i/o tensors) or vectors of transforms.
  \item
    \begin{quote}
      Referee:
      The algorithm description in Section 2.2 is unacceptable. It mentions the
      arithmetic complexity only.
    \end{quote}
    Memory requirements strongly depend on the precomputation technique
    employed. NFFT 3 offers different strategies here ranging from no
    precomputation at all (everything evaluated on-line) to
    full precomputation (can be expensive in terms of memory). In
    Section 2.4 (which was 2.2), we now include a forward reference to
    Appendix 2.3 where details are given.
  \item
    \begin{quote}
      Referee:
      It fails to specify the essential algorithm components. It
      uses the standard FFT, which is preceded by a numerical
      re-sampling step with arithmetic complexity proportional linearly
      to the data size.
    \end{quote}
    The last paragraph of Section 2.4 (was 2.2) now briefly mentions
    the essential components of the NFFT algorithm. For details, we still refer the
    reader to Appendix A.2.
  \item
    \begin{quote}
      Referee:
      Unlike the FFT, the complexity grows fast with the dimensionality.
    \end{quote}
    A $d$-dimensional FFT of degree $N$ (in each dimension) has a complexity of
    $\mathcal{O}(N^{d} \log N)$.
    A $d$-dimensional NFFT of degree $N$ (in each dimension) with $M$ nodes has
    a complexity of $\mathcal{O}(N^{d} \log N + |\log\varepsilon|^d M)$. Both
    algorithms grow exponentially with the number of dimensions $d$. But it is
    true that for the NFFT, also the constant $|\log\varepsilon|^d$ in front
    of the number of nodes $M$ grows exponentially which does not happen in
    the FFT.
  \item
    \begin{quote}
      Referee:
      In addition, an algorithm shall be described with companion
      data structures and the features of algorithm parameters.
      Specifically, the re-sampling factor shall be singled out at least
      and explained.
    \end{quote}
    The last paragraph of Section 2.4 (was 2.2) now mentions the oversampling
    factor and the truncation parameter. For details, we still refer the reader to
    Appendix A.3. The chief aim of this article is to describe the math behind the NFFT
    routines implemented in the NFFT 3 library, as well as basic usage principles
    and applications. We do not think it would serve the purpose of
    the paper to give details of the implementation and technical concerns.
  \item
    \begin{quote}
      Referee:
      There are many typos and grammar errors. (Need a professional
      proof-reader to help out.)
    \end{quote}
    We have done our best to fix the mistakes.
  \item
    \begin{quote}
      Referee:
      Performance metrics and comparison objectives shall be clearly
      noted.
    \end{quote}
    As mentioned, our aim is not to describe all details of the implementation.
    But we now summarise performance related tests in Section 5. The focus is
    to observe how the NFFT algorithm does behave in comparison to the
    FFT and to the direct evaluation NDFT.

    It is nevertheless true that more extensive numerical tests at a
    mature state of the library are desirable. At the current stage, an
    extensive and in-depth performance analysis is not available.
  \item
    \begin{quote}
      Referee:
      This manuscript uses more space on examples and applications.
      It will serve the purpose of the paper if the examples and applications
      are used to demonstrate the range of functions and their
      parameters and the scope of performance tuning the library supports.
      The complexity in terms of arithmetic operations explains
      only why the fast algorithms are implemented, but does not say
      how well they are implemented in this particular software library.
    \end{quote}
    Clearly, the numerical results support the theoretical complexity
    and error estimates.
    New columns in Table 5.2 have been added to show that the NFFT
    is only a reasonable factor slower than the FFT.
    Moreover, our library is open source (i.e., improvements are very welcome)
    and it is to the best of our knowledge the only available implementation
    (besides various \textsc{MatLab}-implementations).
  \item
    \begin{quote}
      Referee:
      There are two fundamental assumptions/limitations (a) the sample
      locations for higher-dimensional FFTs on unequispaced be on
      a Kronecker grid and (b) the sample data be in linearized and
      consecutively packed data arrays.
    \end{quote}
    See comments above.
  \item
    \begin{quote}
      Referee:
      No README file or other documentation is found in the third
      party code directory.
    \end{quote}
    Had been added in the meantime.
  \item
    \begin{quote}
      Referee:
      No explicit mention of using the third party code FFTW, although
      it is mentioned in the installation section.
    \end{quote}
    We now mention the internal use FFTW in Sections 1 (first paragraph) and
    2.4 (last paragraph).
  \item
    \begin{quote}
      Referee:
      The input and output data structures for high-dimensional transforms
      are not clear, especially, on each particular type of grids,
      such Cartesian grid or spherical grid.
    \end{quote}
    The referee is right in that details of input and output data
    structures for generalisations of the NFFT (NFSFT, NNFFT,...)
    are not given explicitly. Details are found in the API
    documentation acompanying the downloadable software package.
    We do not think that it would improve the paper to mention
    the same here.
\end{itemize}

\end{document}
