仅采用输入或输出点的子集高效计算离散傅里叶变换

讨论了在输入和输出数据点数量不同时高效计算离散傅里叶变换（DFT）的方法。确定输入序列长度或输出序列长度是否减少的两个问题可以被发现是互为对偶的，并且在很大程度上可以使用相同的方法来解决。算法利用输入或输出中的冗余，将操作次数降低到比快速傅里叶变换（FFT）算法更少。讨论了常见的修剪方法，并引入了一种高效算法，称为变换分解。它基于标准FFT算法和等效于戈茨尔算法的霍纳多项式评估方案的混合。它需要更少的操作，并且比修剪更灵活。该算法适用于二次幂和质因数算法，以及实输入数据。