快速 Fourier 变换

FFT 不是一种新的变换，而是利用单位根的对称性快速计算离散 Fourier 变换。从系数表示切换到单位根上的点值表示后，多项式乘法变成逐点乘法；把偶数次与奇数次系数拆开后，在 $n$ 次单位根上的两个半规模求值可复用，因为 ${\omega }_n^{k+n/2}=-{\omega }_n^k$，而单位根平方后又折半。递归由此把 $n^2$ 次直接求和降为 $n\log n$，本质是结构化线性变换的分治。

对长度分别为 $r,s\ge 1$ 的两个系数向量，取二次幂 $N\ge r+s-1$ 并补零。两次正变换、逐点相乘和一次逆变换得到它们的线性卷积公理库离散卷积Discrete convolution · Sequence convolution对所有下标分解求和得到序列、概率质量函数或多项式系数的卷积。：一般长度 $N$ 的 DFT 乘积对应模 $x^N-1$ 的循环卷积，而这里乘积次数小于 $N$，没有系数绕回低位。

例如 $a=(1,2,3,4)$，${\omega }_4=i$。偶部 $(1,3)$ 的 DFT 为 $(4,-2)$，奇部 $(2,4)$ 的 DFT 为 $(6,-2)$，蝶形给出

使用负号单位根并除以 $4$ 就恢复原向量。若只把正变换的符号改掉，两个非实坐标会互换；因而符号与归一化是输入输出接口的一部分。

DFT 的代数定义与 FFT 的 $O(n\log n)$ 运算计数都以精确算术为基准；机器实现遵循标准浮点运算模型公理库浮点算术标准误差模型Standard floating-point arithmetic model以每次基本运算的小相对扰动和 gamma 记号组织多步浮点误差分析。时，每个蝶形还会引入舍入误差。整数卷积若要通过舍入恢复精确值，须证明每个实部误差小于 $1/2$；拆位或满足单位根条件的数论变换（NTT）提供另外的实现路线。补零长度不足以覆盖卷积结果次数时会得到循环卷积。经典 radix-2 实现要求长度为二次幂，其他长度可用 mixed-radix 或 Bluestein 等方法。DFT 定义中的正负号与归一化约定也必须前后一致。

FFT 结合序列公理库序列Sequence以自然数为定义域的函数。、复数公理库复数Complex number形如 a+bi 的数，按坐标规则构成实数域的二次扩张。与分治法公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。，用于快速多项式乘法、信号频谱、大整数乘法、生成函数算法和字符串相关计算；数论变换则在有限域中复现单位根结构，避免浮点误差。它计算的是有限循环群上的 DFT；Fourier 级数公理库Fourier 级数Fourier series · 傅里叶级数把周期函数投影到整数频率的正交指数基上所得的离散频谱展开。处理周期函数的无穷展开，Fourier 变换公理库Fourier 变换Fourier transform · 傅里叶变换把非周期函数分解为连续频率成分，并将卷积和平移不变算子转为频域乘法。处理非周期函数的连续频率积分，三者共享频率分解思想，却有不同的对象、归一化与收敛问题。

量子 Fourier 变换公理库量子 Fourier 变换Quantum Fourier transform · QFT从有限 Fourier 矩阵的酉性与二进制分解推导 Hadamard、受控相位门和位反转电路，并区分振幅变换与经典输出。与 FFT 共享有限 Fourier 矩阵，但输入输出接口不同：FFT 读取并返回整个经典复数向量，QFT 则对已经制备好的振幅态施加归一化 Fourier 矩阵，输出仍是量子态。态制备和读出全部经典系数的成本须另计，量子门数不能直接替代本页的完整向量计算成本。

FFT 的卷积接口还通向子集卷积公理库子集卷积subset convolution · fast subset convolution对一个集合的互补子集划分求卷积，并用按秩 zeta 与 Möbius 变换加速全部子集答案。，但后者的“加法”发生在子集并分拆上，需 Möbius/zeta 变换，不能直接把数组下标卷积公式照搬。超比较整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。有时使用字级打包、多项式评估或卷积子程序；这不表示一般 FFT 排序，也不绕过任意比较键的决策树下界，模型仍须保留有限字长与整数操作。

有限循环群上的加性能量公理库加性能量Additive energy · 加法能量用相同和的有序四元组计数衡量加法碰撞，并通过卷积平方和与 Fourier 四阶矩连接和集大小及频谱结构。提供了一个四阶矩应用：若采用不归一化 DFT，集合指示数组满足 $E(A)=n^{-1}\sum _k|\widehat{1_A}(k){|}^4$。当群阶 $n$ 为二次幂时，本页的 radix-2 FFT 可以从频谱计算有多少有序四元组满足 $a+b=a^{\prime }+b^{\prime }$；若输入代表整数集合，仍须选择足够大的周期，避免不同整数和被模运算合并。

FFT 加速的离散卷积会按网格长度折叠频率。谱混叠与去混叠公理库谱混叠与去混叠Spectral aliasing · Dealiasing从频率模网格数的折叠推导二次非线性的补零与截断规则，完整算出一个伪低频反例。用单模态平方展示一个伪低频，并从保留带范围推导二次非线性的补零与截断规则。