Multidimensional polynomial transform algorithm for multidimensional DFT

A method is presented for converting the m-dimensional discrete Fourier tra nsform (MD-DFT) into a number of one-dimensional DFTs (1D-DFTs) by rearrang ing the order of the input sequence. The result of this conversion is that the number of multiplications for computing an m-dimensional DFT is only 1/ m times that of the usually used row-column DFT algorithm. To reduce the nu mber of additions, a multidimensional polynomial transform (MD-PT) is then used and a considerable saving in the number of addition operations is also achieved.