什么是DFT

DFT（Discrete Fourier Transform），即离散傅里叶变换，是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。

什么是FFT

FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换（DFT）的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

什么是FFTW

FFTW ( the Faster Fourier Transform in the West)是一个快速计算离散傅里叶变换的标准C语言程序集，其由MIT的M.Frigo和S. Johnson开发。可计算一维或多维实和复数据以及任意规模的DFT。

官网地址：传送门 (opens new window)，下载地址：传送门 (opens new window)。

目前最新版本为 Version 3.3.6 is the latest stable release of FFTW ( 截止2017-04-30）

FTW库所需的编译环境

Intel Compiler /GNU Compiler + MPI Compiler （如果编译mpi版的fftw）

默认编译

安装fftw仅需要遵循常见的三步骤即可（configure+make+make install），在这里先介绍一下默认安装，再然着重介绍一些configure的配置选项。

以fftw-3.3.6-pl2.tar.gz为例，先从官网下载该压缩包。解压缩，并进入源码目录进行编译即可。

tar zxvf fftw-3.3.6-pl2.tar.gz  
cd fftw-3.3.6-pl2  
./configure  
make  
make install  

这样就可以把fftw库按照默认配置，安装到默认的路径下。 使用的是GNU的编译器，安装到的是/usr/local下面。

优化编译参数介绍

但是，我们通常会依据./configure -help得到的信息来添加一些参数来达到优化编译的目录。 接下来我们使用命令查看一些常用配置参数：

设定安装目录

Installation directories:
--prefix=PREFIX    install architecture-independent files in PREFIX[/usr/local]

是否编译动态库

Optional Features:
--enable-shared[=PKGS]    build shared libraries [default=no]

是否编译静态库

--enable-static[=PKGS]    build static libraries [default=yes]

是否编译单精度版本

--enable-single         compile fftw in single precision
--enable-float          synonym for --enable-single

开启针对特定机器架构的优化，这个取决于机器CPU（下面有介绍）。

--enable-sse            enable SSE optimizations
--enable-sse2           enable SSE/SSE2 optimizations
--enable-avx            enable AVX optimizations
--enable-avx2           enable AVX2 optimizations
--enable-neon           enable ARM NEON optimizations

开启积和熔加运算(Fused Multiply-Add/FMA)的优化

--enable-fma            enable optimizations for machineswith fused multiply-add

是否编译mpi版的fftw库

--enable-mpi            compile FFTW MPI library

是否使用OpenMP指令进行并行

--enable-openmp         use OpenMP directives for parallelism

是否编译FFTW SMP线程库

--enable-threads        compile FFTW SMP threads library

这部分是指定编译器及编译参数，默认是用GNU的编译器：

Some influential environment variables:
  CC          C compiler command
  CFLAGS      C compiler flags
  CPP         C preprocessor
  MPICC       MPI C compiler command
  F77         Fortran 77 compiler command
  FFLAGS      Fortran 77 compiler flags

为了用intel的编译器，我们需要特别指定一下：CC=icc F77=ifort，相关的参数通常保持默认即可。

备注： 1）如何查看CPU是否支持某个指令集呢？使用如下命令可以列出支持的指令集名称

cat /proc/cpuinfo | grep flags | uniq

2）SIMD SIMD单指令流多数据流(SingleInstructionMultiple Data,SIMD)是一种采用一个控制器来控制多个处理器，同时对一组数据（又称“数据向量”）中的每一个分别执行相同的操作从而实现空间上的并行性的技术。

MMX是由英特尔开发的一种SIMD多媒体指令集，SSE（Streaming SIMDExtensions）是MMX的扩充指令集，AVX（Advanced VectorExtensions）是Intel的SSE延伸架构，FMA（Fused MultiplyAccumulate）是Intel的AVX扩充指令集。

NEON实际上是ARM的SIMD（Single InstructionMultiple Data）技术的延续，它是一个结合64和128 bit的SIMD（Single InstructionMultiple Data 单指令多重数据）指令集。

优化编译单精度版本

./configure --prefix=$HOME/software/fftw/3.3.6-pl2-icc13 \  
  CC=icc F77=ifort \  
  --enable-shared --enable-static \  
  --enable-float \  
  --enable-sse --enable-sse2 \  
  --enable-avx --enable-avx2 --enable-fma \  
  --enable-mpi \  
  --enable-threads--enable-openmp  
make  
make install  

优化编译双精度版本

./configure --prefix=$HOME/software/fftw/3.3.6-pl2-icc13 \  
  CC=icc F77=ifort \  
  --enable-shared --enable-static \  
  --enable-sse2 --enable-avx --enable-avx2 --enable-fma \  
  --enable-mpi \  
  --enable-threads--enable-openmp  
make  
make install

编译一些需要fftw的软件

通常会用到的是libfftw.a以及一些头文件，在编译或链接的时候，给出它的路径即可。

比如： gromacs软件：

  -DFFTWF_LIBRARY="$HOME/software/fftw/3.3.6-pl2-icc13" 
  -DFFTWF_INCLUDE_DIR="$HOME/fftw/include/"  

这里介绍的是官网题的fftw库，我们还可以使用Intel MKL库中的fftw接口。