NFFT - Nonequispaced FFT

Overview

NFFT is a software library, written in C, for computing non-equispaced fastFourier transforms and related variations. It implements the followingtransforms:

1. Non-equispaced fast Fourier transform (NFFT)

   • forward transform (NFFT), i.e. frequency to time/space domain
   • adjoint transform (adjoint NFFT), i.e. time/space to frequency domain

2. Generalisations

   • to arbitrary nodes in time and frequency domain (NNFFT)
   • to real-valued data, i.e. (co)sine transforms, (NFCT, NFST)
   • to the sphere S^2 (NFSFT)
   • to the rotation group (NFSOFT)
   • to the hyperbolic cross (NSFFT)

3. Generalised inverse transformations based on iterative methods, e.g. CGNR/CGNE

Some examples for application of these transforms are provided:

1. Medical imaging

   • magnetic resonance imaging (mri)
   • computerised tomography (radon)

2. Summation schemes

   • fast summation (fastsum)
   • fast Gauss transform (FGT)
   • singular kernels
   • zonal kernels

3. polar FFT, discrete Radon transform, ridgelet transform

Detailed API documentation in HTML format can be found indoc/html/index.html, if you are working from a release tarball.When working from a source repository, the documentation can begenerated with Doxygen.

make doc

Building

The NFFT depends on the FFTW library, which is available for many Linux distros, Homebrew on macOS and MSYS2 on Windows. If you compile the FFTW yourself, it should be configured --enable-shared.

When working from a source repository, you need to run libtoolize and autoreconf first. A bash script to do this is provided.

./bootstrap.sh

The rest of the build process is standard.

./configure --enable-all --enable-openmp [add options as necessary, see below]

Alternatively, you might run the configure script for Matlab.

./configure --enable-all --enable-openmp --with-matlab=/path/to/matlab

Here are some useful optional flags for ./configure:

• --enable-all specifies that all modules should be compiled,
• --enable-openmp enables the multicore support and
• --enable-julia specifies that the julia interface will be compiled.
• --with-matlab=path/to/matlab specifies a path of Matlab, and
• --with-octave=path/to/octave does the same for GNU Octave.
• For a list of all available options, run ./configure --help.

Build the software.

make

Optionally, unit tests may be run.

make check

Optionally, install NFFT on your system.

make install

Citing

The most current general paper, the one that we recommend if you wish to cite NFFT, is Keiner, J., Kunis, S., and Potts, D.''Using NFFT 3 - a software library for various nonequispaced fast Fourier transforms''ACM Trans. Math. Software,36, Article 19, 1-30, 2009.

Feedback

Your comments are welcome! This is the third version of the library and maynot be as robust or well documented as it should be. Please keep track of bugsor missing/confusing instructions and report them toDaniel Potts.The postal address is

  Prof. Dr. Daniel Potts
  TU Chemnitz, Fakultaet fuer Mathematik
  Reichenhainer Str. 39
  09107 Chemnitz
  GERMANY

Alternatively, you might contactStefan KunisorJens Keiner.

If you find NFFT useful, we would be delighted to hear about what applicationyou are using NFFT for!

Legal Information & Credits

Copyright (c) 2002, 2017 Jens Keiner, Stefan Kunis, Daniel Potts

This software was written by Jens Keiner, Stefan Kunis and Daniel Potts.It was developed at the Mathematical Institute, University ofLuebeck, and at the Faculty of Mathematics, Chemnitz University of Technology.

NFFT3 is free software. You can redistribute it and/or modify it under theterms of the GNU General Public License as published by the Free SoftwareFoundation; either version 2 of the License, or (at your option) any laterversion. If not stated otherwise, this applies to all files contained in thispackage and its sub-directories.

This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See theGNU General Public License for more details.

You should have received a copy of the GNU General Public Licensealong with this program; if not, write to the Free SoftwareFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

Directory structure