Efficient algorithms for computing linear convolutions based on the fast Fourier transform are developed. A hybrid approach is described that combines the conventional practice of explicit dealiasing (explicitly padding the input data with zeros) and implicit dealiasing (mathematically accounting for these zero values). The new approach generalizes implicit dealiasing to arbitrary padding ratios and includes explicit dealiasing as a special case. Unlike existing implementations of implicit dealiasing, hybrid dealiasing tailors its subtransform sizes to the convolution geometry. Multidimensional convolutions are implemented with hybrid dealiasing by decomposing them into lower-dimensional convolutions. Convolutions of complex-valued and Hermitian inputs of equal length are illustrated with pseudocode and implemented in the open-source FFTW++ library. Hybrid dealiasing is shown to outperform explicit dealiasing in one, two, and three dimensions.
翻译:本文提出了一种基于快速傅里叶变换计算线性卷积的高效算法。该文介绍了一种混合方法,将显式去混叠(在输入数据中明确填充零)和隐式去混叠(在数学上考虑这些零)相结合。新方法将隐式去混叠推广到任意的填充比率,并将显式去混叠作为一种特殊情况。与现有的隐式去混叠实现不同,混合去混叠将其子变换大小适应于卷积几何。多维卷积使用混合去混叠通过将其分解为低维卷积而实现。通过伪代码和在开源FFTW++库中的实现,演示了相等长度的复值和反厄米输入的卷积。混合去混叠在一维、二维和三维中表现出优于显式去混叠的性能。