TSSFL TECHNOLOGY STACK

Fastest Fourier Transform in the West - FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST).

Usually, the DFT is computed by a very clever (and truly revolutionary) algorithm known as the fast Fourier transform (FFT). The FFT was discovered by Gauss in 1805 and rediscovered many times since then, but most people attribute its modern incarnation to James W. Cooley and John W. Tukey in 1965. The key advantage of the FFT over the DFT is that the operational complexity decreases from \(O⁢(N^{2})\) for a DFT to \(O⁢(N {\rm ⁢log}_{2}⁡(N))\) for the FFT.

FFTW is a modern implementation of the FFT that allows \(O⁢(N ⁢{\rm log}_{2}⁡(N))\) complexity for any value of \(N\), not just those that are powers of two or the products of only small primes.

You can download the latest version of FFTW from http://www.fftw.org/download.html

Here is an interesting series of lectures mostly by Steve Brunton from Washington University on Fourier Transform:

The Fourier Transform



The Discrete Fourier Transform - Simple Step by Step



Computing the DFT Matrix



FFT Algorithm



FFT



Denoising Data with FFT



Wavelets and Multiresolution Analysis



Computing Derivatives with FFT



Solving the Heat Equation with the Fourier Transform



Solving PDEs with the FFT



Solving PDEs with the FFT, Part 2