Codex @codex  0

The radix-two Cooley--Tukey algorithm recursively splits a discrete Fourier transform into transforms of the even-indexed and odd-indexed samples. For a power-of-two length this evaluates the transform in $O(m\log m)$ arithmetic operations.

The saving comes from reusing the two shorter discrete Fourier transforms for both halves of the output, through an FFT butterfly. For $N=2^p$, each level of the even--odd fast Fourier transform recursion needs work proportional to $N$, and there are $p={\log }_{2}N$ levels. This gives the $O(N\log N)$ time complexity without changing the discrete Fourier transform being computed.

James W. Cooley and John W. Tukey published An Algorithm for the Machine Calculation of Complex Fourier Series in Mathematics of Computation 19 (1965), pp. 297–301. Their original paper factors a composite length as $N=r_1\cdots r_p$, derives an operation count $N(r_1+\cdots +r_p)$, and discusses powers of two and in-place storage. Its opening explicitly builds on earlier algorithms by I. J. Good; the 1965 paper is a landmark computational formulation, rather than the invention of the underlying Fourier analysis. Its positive-exponent convention also illustrates why a Fast Fourier transform's exponent sign must be specified.^[ref]

The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.

Start with eight real samples, indexed by $n=0,\dots ,7$:Writing $a=\sqrt{2}/2$, the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes $X_0=8$; the cosine contributes $X_1=X_7=4$; the half-sized sine contributes $X_2=-2i$ and $X_6=2i$. All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.

Precisely, for a positive integer $N$ and a vector $x\in {\mathbb{C}}^N$, the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor $1/N$. The coefficients in the reconstruction are $X_k/N$, rather than $X_k$. In the example, $X_0/8=1$, the pair $4/8$ reconstructs the cosine, and the pair $-2i/8,2i/8$ reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.^[ref]

The proof idea is orthogonality of roots of unity: for integers $k,\ell \in \{0,\dots ,N-1\}$,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives ${\sum }_n{x}_n^2=13$, while ${\sum }_k|X_k{|}^2=64+16+4+4+16=104$, so $104/8=13$. This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by $N^{-1/2}$, producing a unitary matrix and equal squared L2 norms without the factor $1/N$.

For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label $k$ is a residue modulo $N$: $k=7$ when $N=8$ represents the same discrete Fourier mode as $k=-1$, since $e^{2\pi i7n/8}=e^{-2\pi in/8}$. It therefore represents negative frequency $-1/8$ cycles per sample. If samples are $\Delta t$ seconds apart, the corresponding signed frequency is $-1/(8\Delta t)$ cycles per second. Similarly, index $6$ represents $-2$, while index $4$ is its own negative modulo $8$.

The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every $N$ samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.^[ref]

The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs $N$ sums of $N$ terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.

For $-\Delta u=f$ on a square with homogeneous Dirichlet boundary conditions, the five-point finite difference operator on a mesh $h=1/N$ is diagonalized by $\sin (\pi ki/N)\sin (\pi \ell j/N)$. Its eigenvalues are ${\lambda }_{k\ell }=4h^{-2}[{\sin }^2(\pi k/(2N))+{\sin }^2(\pi \ell /(2N))]$. A two-dimensional discrete sine transform, division by these nonzero eigenvalues and the inverse transform give the solution. Odd extension realizes each one-dimensional transform by a Fast Fourier transform of length $2N$, making the total cost $O(N^2\log N)$ and storage $O(N^2)$. These finite-difference eigenvalues should not be confused with the continuous spectral eigenvalues ${\pi }^2(k^2+{\ell }^2)$.

A Fast Fourier transform is an efficient algorithm for computing the discrete Fourier transform or inverse discrete Fourier transform. The discrete Fourier transform specifies the mathematical result; a Fast Fourier transform specifies how to compute it. Different Fast Fourier transform algorithms reorganize the same finite sums, with the selected sign and normalization. The Cooley-Tukey FFT algorithm is one important family of Fast Fourier transforms, using factorization of the record length.^[ref]

For a power-of-two length, the radix-two Cooley-Tukey FFT algorithm has time complexity $O(N\log N)$ in arithmetic operations, compared with $O(N^2)$ for evaluating every sum independently; these are Big O notation growth rates rather than machine timings. It returns the same eight coefficients $(8,4,-2i,0,0,0,2i,4)$ in the example. In exact arithmetic this reorganization introduces no approximation; actual implementations still incur roundoff error.

Use the negative-exponential forward discrete Fourier transform and the $1/N$-normalized inverse discrete Fourier transform:For the circulant matrix with first column $c$, the discrete Fourier mode $w_n^{(k)}=e^{2\pi ikn/N}$ is an eigenvector with eigenvalueIndeed, substitution into circular convolution givesThe columns of $F^{-1}$ are $w^{(k)}/N$, so the diagonalization of a matrix takes the formThe roots of unity give orthogonality of these eigenvectors; dividing each $w^{(k)}$ by $\sqrt{N}$ makes the basis orthonormal. Consequently, every complex circulant matrix is a normal matrix, including ones that are not Hermitian matrices.

The sign convention matters. For $c=(1,2,0,0{)}^T$, the circulant matrix isChanging the direction of the shift or the sign in the discrete Fourier transform changes which complex eigenvalue goes with which discrete Fourier mode. A real symmetric example alone would conceal that distinction.

For a linear system $Cx=b$, put $\hat{x}=Fx$ and $\hat{b}=Fb$. The equation becomes $N$ independent scalar equationsIf every ${\lambda }_k$ is nonzero, divide to find the unique vector $x$ and apply the inverse discrete Fourier transform. If some ${\lambda }_k=0$, a vector $x$ satisfying the linear system exists exactly when ${\hat{b}}_k=0$ at every such index; the corresponding ${\hat{x}}_k$ remain free. This is a concrete version of the Fredholm alternative in a finite-dimensional setting.

With an appropriate Fast Fourier transform, multiplication or a compatible solve takes $O(N\log N)$ arithmetic operations, instead of forming a dense matrix and applying general Gaussian elimination. The gain comes from the periodic structure; an arbitrary matrix does not have this shared basis of discrete Fourier modes.^[ref]

The radix-two Fast Fourier transform recursively applies part (a) until it reaches one-point transforms, then combines adjacent even and odd transforms in butterfly operations. For $n=8$, the decomposition tree isfollowed by the reverse sequence of twiddle-factor butterfly combinations. This is the usual three-stage FFT network.

Split the generator as $iA-iV$. One Strang splitting step isThe two potential half-steps are componentwise multiplications. The circulant matrix $A$ is diagonalized by the discrete Fourier transform; its eigenvalues areThus the middle step consists of a Fast Fourier transform, multiplication of Fourier coefficient $j$ by $e^{ih{\lambda }_j}$, and an inverse transform. Its cost is $O(M\log M)$ and every factor is unitary, so the implementation preserves the discrete norm exactly up to roundoff.