FFTW

From HP-SEE Wiki

Latest revision as of 15:15, 5 August 2011

• Web site: http://www.fftw.org/
• Described version: 3.3
• Licensing: GNU General Public License v2
• User documentation: http://www.fftw.org/fftw3_doc/
• Download: http://www.fftw.org/download.html
• Source code: http://www.fftw.org/fftw-3.3.tar.gz

Authors/Maintainers

• The FFTW package was developed at MIT by Matteo Frigo and Steven G. Johnson.

Summary

The Fastest Fourier Transform in the West (FFTW) is a comprehensive collection of C routines for computing the discrete Fourier transform (DFT) and its various special cases. According to the benchmarks publicly available on the Internet, FFTW is faster than other FFT implementations available, even those which are vendor-tuned (http://www.fftw.org/benchfft/). To achieve this performance, FFTW uses special self-optimization techniques, such that it learns the fastest way to compute on a specific hardware. This task is performed by a planner that produces a data structure containing the information needed to achieve best possible performance. FFTW computes complex, real, symmetric, multidimensional and parallel transforms, and it can also handle arbitrary array sizes efficiently. FFTW received the 1999 J. H. Wilkinson Prize for Numerical Software, which is awarded every four years to the software that "best addresses all phases of the preparation of high quality numerical software." FFTW is probably the most flexible discrete Fourier transformation (DFT) package available.

Features

• Written in C, making it portable and running well on many architectures and operating systems;
• Has interfaces for both C and Fortran;
• Does not have any limitation to the dimension (rank) of a transform;
• Supports multiple-strides DFTs;
• Supports the discrete cosine transforms and discrete sine transforms;
• Adapts to the hardware it runs on;
• Supports parallel transforms (pthreads, OpenMP, and, as of this version, MPI);
• Supports SSE/SSE2/Altivec, since version 3.0. Version 3.3 supports AVX SIMD instructions.

Architectural/Functional Overview

• High level design info is available in the following paper: http://www.fftw.org/fftw-paper-ieee.pdf

Usage Overview

• http://www.fftw.org/fftw3_doc/Tutorial.html#Tutorial

Dependencies

• Should be compiled with the same compiler used to compile the application. Cross-linking is possible, but might affect the performance.
• If parallel transforms are to be used, the appropriate parallel libraries (OpenMP, MPI) should be installed.

HP-SEE Applications

• NUQG (Numerical study of ultra-cold quantum gases)

Resource Centers

• BG, BG
• HPCG, BG
• IFIN_Bio, RO
• NCIT-Cluster, RO
• NIIFI SC, HU
• PARADOX, RS

Usage by Other Projects and Communities

• FFTW is very widely used by innumerable communities, since it provides essential mathematical capability vital for many algorithms.

Recommendations for Configuration and Usage

• Should be configured with --enable-sse2 flag.
• Compiling OpenMP support (--enable-openmp) now installs a fftw3_omp library, instead of fftw3_threads, so that OpenMP and POSIX threads (--enable-threads) libraries can be built and installed at the same time.
• In order to resolve differences in the ordering of higher-dimensional arrays in C and Fortran, FFTW requires that the data are always organized into a one-dimensional array. The ordering therefore can be done according to the preference of the application developer. The dimensionality is specified by the variable usually called rank, and the number of data elements in each dimension is specified by an array, usually called rankn.
• Useful link for properly organizing your data (centered, non-centered, multi-dimensional) before invoking one of FFTW functions can be found here: http://qwiki.stanford.edu/index.php/Fourier_Transform_How_To