Understand Fast Fourier Transform

Fast Fourier transform (FFT) always gives me a headache because of the many implicit units and normalization conventions. To figure out forward transform, first try FT a 1D Gaussian, then try FT a 3D Gaussian. To figure out reverse transform,

obsolete: this document compares the FFT algorithm in quantum espresso with that in Python will demonstrate how one may figure out those implicit definitions.

Units

The standard FFT takes an array to another array with the same length. The first thing one has to understand is the physical meaning of those numbers. This can be confusing because the same FFT algorithm is used across many disciplines. For example, in signal processing, the two arrays have units of time and frequency, whereas in condensed matter, the two arrays have real space (position) and reciprocal space units (momentum).

In condensed matter, consider a 1D box of length L. For an FFT grid of size N, the real space spacing is dx = L/N. The reciprocal space box length is \(2\pi N/L\), so the spacing is dk = \(2\pi/L\).

Ordering

Standard ordering of a 1D FFT grid of size N has origin of real/reciprocal space at 0, lowest positive frequency at 1 and lowest negative frequency at N-1. This is nice because one can map integer representation of reciprocal lattice vectors directly to FFT grid index.

Normalization

One common normalization scheme (in condensed matter) is to require each plane wave basis function to normalize to 1 over real space volume.