Multidimensional fast Fourier transform algorithm for signals with arbitrary symmetries

A multidimensional fast Fourier transform (FFT) algorithm is presented for signals with arbitrary symmetries and periodic on arbitrary lattices. Appli cations that can benefit from such an algorithm include Volterra filtering and analysis of x-ray diffraction data. The presented algorithm exploits si gnal redundancy to achieve a computational complexity of N log N, where N i s the number of independent samples. To the authors' knowledge, this is the only FFT that; makes the frequency domain computation of Volterra filterin g more convenient than the time domain approach. (C) 1999 Optical Society o f America [S0740-3232(99)02108-0].