Fast Fourier Transform

Hide code cell content

 
import mmf_setup;mmf_setup.nbinit()
import logging;logging.getLogger('matplotlib').setLevel(logging.CRITICAL)
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
try: 
    from myst_nb import glue
except ImportError: 
    glue = None

This cell adds /home/docs/checkouts/readthedocs.org/user_builds/wsu-phys-581-computation/checkouts/latest/src to your path, and contains some definitions for equations and some CSS for styling the notebook. If things look a bit strange, please try the following:

  • Choose "Trust Notebook" from the "File" menu.
  • Re-execute this cell.
  • Reload the notebook.

Fast Fourier Transform#

Consider performing the discrete Fourier transform (DCT) \(\tilde{f}_{m}\) of a periodic function tabulated at \(N\) equally spaced points \(f_n = f(x_n)\):

\[\begin{gather*} \tilde{f}_{m} = \sum_{n} \underbrace{e^{-2\pi \I mn/N}}_{F_{mn} = [\mat{F}]_{mn}}f_n, \qquad m, n \in {0,1,\dots, N-1}. \end{gather*}\]

Naïvely, this is simply matrix multiplication, which requires \(O(N^2)\) operations.

The fast-Fourier transform (FFT)