Content Hotkeys
Nonequispaced fast Fourier transform

NFFT Frequently Asked Questions with Answers

This is the list of Frequently Asked Questions about NFFT.

Using NFFT

  • Number of irregular samples (nodes), number of regular samples (frequencies)
    The cut-off frequency (length of the regular grid) is N, i.e. the total number of regular samples is the product of N[0],...,N[d-1]. The number of irregular samples (nodes) is M.
  • How do I convert my nonuniformly/irregularly sampled data from time/spatial domain to frequency domain?
    First of all, please note that our definition of the NDFT/NFFT forward transform and its inverse is exactly the opposite of the FFTW notation. This means our NDFT/NFFT forward transform converts from a regular grid in frequency domain to (potentially) nonuniform/irregular evaluation nodes in time/spatial domain.
    Moreover, since the NDFT/NFFT is not an orthogonal transform in general, its adjoint version is not the inverse transform.
    In order to perform an inverse NDFT/NFFT, which transforms nonuniformly/irregularly sampled data from spatial/time domain to a regular grid in frequency domain, please have a look at the documentation of the inversion, the NFFT 3 manual, and some more details on the theoretical background in Chapter 5 of the PhD thesis of Stefan Kunis. An example on how to use the inverse NFFT can be found in examples/solver/simple_test.c of our NFFT software library. Additionally, for the one-dimensional case, there is a new direct inversion method based on fast summation for Matlab/Octave, available in our latest release.


Known Issues

  • Inaccurate calculations in long double precision with OpenMP in Windows
    The NFFT with long double precision and OpenMP in Windows does many calculations only in double precision. This is caused by a bug in MinGW. Other operating systems are not affected.
    If you compile long double precision in Windows, please disable OpenMP support (configure switch "--disable-openmp" which is the default).
  • Internal compiler error when compiling fastsum
    Due to a bug in GCC versions 7.1.0, 7.2.0 and 7.3.0, compilation of the NFFT might abort with an internal compiler error in the fastsum module. A workaround was added in NFFT 3.4.0.
  • Wrong NFFT calculation when enabling the debug mode or overriding the compiler flags (CFLAGS)
    Due to a bug in GCC versions 4.5.0, 4.5.1, 4.5.2, 4.5.3, 4.6.0 and 4.6.1, compiling the NFFT without the compiler flag "-ffast-math" may lead to incorrect computation results and buffer overflows.
    By default, this flag is set by the "configure" script.
    If you enable the debug mode (configure switch "--enable-debug") or set the CFLAGS manually, please add the compiler flag "-ffast-math" to the CFLAGS environment variable.
  • Internal compiler error when compiling with MRI support
    Due to a bug in GCC version 4.7.1, compilation of the NFFT with MRI module enabled (configure option --enable-mri or --enable-all) will abort with an internal compiler error.
    This problem does not occur in earlier or later versions of the GCC. A workaround was added in nfft-3.2.3.
  • Compilation fails when MRI module enabled and NNFFT module disabled
    When the NFFT is compiled with MRI and without NNFFT support, a compilation error eccurs in applications/mri/mri2d.
    Please also enable the NNFFT module when building with MRI support (configure options --enable-nnfft --enable-mri), or build all modules (--enable-all).

NFFT for Windows

We offer compiled binaries of the NFFT library and Matlab interface for 64-bit Windows on our download page. If you want to compile NFFT by yourself, you can use the following manual which should work with NFFT 3.4.0 on a 64-bit Windows PC with 64-bit Matlab.

  1. Download and install MSYS2.
  2. Start the MinGW-w64 Win64 Shell, and type the following to update your installation and install the MinGW-w64 toolchain and FFTW
    pacman -Syuu
    pacman -S mingw-w64-x86_64-toolchain make mingw-w64-x86_64-fftw
  3. Download and unpack the NFFT source code from the download page to your MSYS2 home directory (e.g. C:\msys64\home\JaneDoe\nfft-3.4.0, replace JaneDoe by your username).
  4. Open the NFFT directory in the MinGW shell
    cd nfft-3.4.0
  5. Run the configure script
    ./configure --enable-all --enable-openmp --with-matlab=/c/Programme/MATLAB/R2017a
    Here are some useful optional flags: --enable-all says that all modules should be compiled, --enable-openmp enables the multicore support, and --with-matlab contains the path to your Matlab installation. For a list of all available options, you can run ./configure --help.
    Note: You might run into trouble if the path of your Matlab installation contains a space (e.g. C:\Program Files). An easy way to overcome this is creating a link to your Matlab directory.
  6. Compile the nfft by running
  7. The compiled programs need the proper libraries to run correctly, i.e., they require libfftw3-3.dll, libwinpthread-1.dll, libgcc_s_seh-1.dll, libgomp-1.dll (all in the folder mingw64/bin, the latter two are only required if openmp is enabled in the configure script). For some executebles, you might also need the .dll file from the directory nfft-3.4.0/.libs. The easiest way to add these libraries is to copy them all in the same directory you run the executeble from. Alternatively, you can put the dll files in a directory added to the Windows %PATH% environment variable (see also How do I set or change the PATH system variable?). When having problems with dependecies, check out the Dependecy Walker.
    Note: When running Matlab, the dll files should be in your current Matlab directory, adding it the Matlab path might be insufficient.