FFT

**FFT Fast Fourier Transform Parallel** is **an efficient algorithm computing discrete Fourier transform in O(N log N) time through recursive decomposition, enabling real-time signal processing and spectral analysis at scale** — workhorse of scientific computing with well-understood parallelization. FFT performance directly enables many applications. **Cooley-Tukey Radix-2 FFT** recursively splits input of size N into N/2 even-indexed and N/2 odd-indexed elements, computes FFTs, combines with twiddle factors (w^k) weighting butterfly operations. Recursive structure fits tree-like parallel decomposition. **Radix-4 and Mixed-Radix** improve cache locality by processing larger blocks per recursion level. Radix-4 reduces memory traffic by factor 1.33 versus radix-2. Mixed-radix (combining radix-2 and radix-4) adapts to problem size factorization. **Parallel Bit-Reversal** permutes input to natural order for in-place FFT. Simple parallel algorithm: each thread computes destination for assigned indices. Efficiently pipelined on GPU. **Butterfly Operations and Stages** after bit reversal, execute log2(N) stages: stage s performs N/2^s butterflies each combining values distance 2^s apart, twiddle factors multiply by e^(-2πi k/2^s). **1D FFT Parallelization** small N (< 10^6): single GPU works well, parallelism within FFT algorithm. Medium N (10^6-10^9): decompose into multiple independent 1D FFTs, embarrassingly parallel. Large N: distributed FFT across GPUs/nodes with all-to-all transpose between stages. **Multi-Dimensional FFT** computes tensor product: 2D FFT = row FFTs followed by column FFTs (or vice versa). Rows/columns computed independently, maximizing parallelism. Transpose between stages permutes data organization. **All-to-All Transpose** between FFT dimensions becomes bottleneck in distributed setting. Optimize through tiling (multiple rows/columns per all-to-all message) and overlapping communication with computation. **Bluestein Algorithm** factors N into coprime factors, computing via FFT of larger size with padding, enabling O(N log N) for prime N and mixed-radix N. Less efficient than Cooley-Tukey for highly composite N but enables flexibility. **In-Place FFT** with carefully ordered stages and temporary storage avoids O(N) extra memory—critical for very large datasets. **Vectorization** and cache optimization: reorder operations to exploit SIMD and cache lines. **Applications** include convolution (FFT-multiply-IFFT), spectral methods solving PDEs, signal processing, and image processing. **Efficient parallel FFT requires careful attention to data layout, communication patterns in distributed setting, and numerical stability of twiddle factor computation** for accurate high-dimensional transforms.