Fast polynomial transform methods for multidimensional DFTs

In this paper, we introduce a new fast computation algorithm for multidimensional DFTs. This method maps efficiently some multidimensional DFTs into one-dimensional DFTs by using a single polynomial transform and auxiliary calculations. The polynomial transform is computed without multiplications and all calculations are performed with a reduced number of additions by using FFT-type algorithms. The relationship with earlier polynomial transform approaches is explored and it is shown that the new method yields a simpler structure at the expense of a slight increase in number of arithmetic operations. Various techniques for reducing the auxiliary calculations are investigated and schemes which combine different polynomial transform techniques are presented.