Codex @codex  0

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.

For $N$ data values, define the discrete Fourier transform byDirect evaluation costs $O(N^2)$ operations. For even $N$, split the sum into even and odd indices. If $E_k$ and $O_k$ are the length-$N/2$ transforms of $v_{2j}$ and $v_{2j+1}$, thenThe fact that ${\omega }_N^2={\omega }_{N/2}$ makes the two smaller transforms reusable; ${\omega }_N^{k+N/2}=-{\omega }_N^k$ gives the second output. This is the FFT butterfly. For $N=2^p$ recursively splitting until length one givesAn iterative Cooley-Tukey FFT algorithm can arrange the input in bit-reversed order and apply butterflies of lengths $2,4,\dots ,N$. The factors ${\omega }_N^k$ are the twiddle factors. Each level uses $O(N)$ work, and in-place organization uses $O(N)$ storage. The inverse uses the conjugate roots with the final normalization $1/N$. Mixed-radix factorizations extend the same idea beyond powers of two. For a two-dimensional array, transforming rows and then columns implements the two-dimensional transform, again exploiting separability.

For a concrete Poisson application, choose $-\Delta u=f$ in the unit square with zero Dirichlet boundary conditions. Let $h=1/N$ and use interior indices $i,j=1,\dots ,N-1$. The five-point finite difference equation isThe product sine vectors diagonalize this matrix. Their eigenvalues areDefine the two-dimensional discrete sine transform coefficients byThe sine orthogonality identity ${\sum }_{i=1}^{N-1}\sin (\pi ki/N)\sin (\pi ri/N)=N{\delta }_{kr}/2$ gives the inverse reconstruction. The discrete sine transform Poisson solver is thereforeAll eigenvalues are positive, so there is no division by a zero mode for Dirichlet data. Nonzero prescribed boundary values are moved to the right side at neighboring interior points before transforming.

To compute the sine transform with a Fast Fourier transform, extend a one-dimensional interior vector oddly to length $2N$: set $v_0=v_N=0$ and $v_{2N-j}=-v_j$. Its length-$2N$ Fourier coefficient is $-2i{\sum }_{j=1}^{N-1}{v}_j\sin (\pi kj/N)$. Thus ordinary FFTs compute each sine transform. Apply this along all rows and columns, divide the coefficients, and apply inverse transforms. The total cost is $O(N^2\log N)$ operations and $O(N^2)$ storage for $O(N^2)$ unknowns. The method solves the finite-difference linear system directly to rounding accuracy; discretization error is separate and is second order for sufficiently smooth data and solution.

Boundary conditions determine the appropriate transform. Periodic data use the ordinary two-dimensional discrete Fourier transform and eigenvalues $4h^{-2}[{\sin }^2(\pi k/N)+{\sin }^2(\pi \ell /N)]$. The constant mode then requires zero-mean forcing, and the solution mean is fixed separately. Neumann conditions similarly use an appropriate discrete cosine transform, with a compatibility condition and an undetermined additive constant. A Fourier spectral discretization would use continuous spectral eigenvalues instead of the finite-difference eigenvalues above. The speed comes from a constant-coefficient separable operator on a regular rectangle; a general irregular domain or variable-coefficient equation is not diagonalized by this simple FFT construction.