Hybrid Dealiasing of Complex Convolutions

.Efficient algorithms based on the fast Fourier transform are developed for computing linear convolutions. 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.Reproducibility of computational results.This paper has been awarded the "SIAM Reproducibility Badge: Code and Data Available" as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available from https://github.com/dealias/fftwpp and in the supplementary materials.Keywordsdealiasinghybrid paddingimplicit paddingzero paddingconvolutiondiscrete Fourier transformfast Fourier transformHermitian symmetric dataMSC codes65R9965T50