Inverse polynomial transform algorithms for DFTs and convolutions

In this paper, we introduce a new fast computation algorithm for multidimensional DFTs. This method uses inverse polynomial transforms to perform an efficient mapping of multidimensional DFTS into one-dimensional DFTs in a way similar to earlier polynomial transform techniques, but with all operations performed in reversed order. This is shown to yield fast DFT algorithms which retain the basic advantages related to the use of polynomial transforms while allowing a significant reduction in round-off noise. We then combine the direct and inverse polynomial transform methods to derive new fast algorithms for multidimensional convolutions.