Novel algorithms for the accurate, efficient, and parallel computation of multidimensional, regional discrete Fourier transforms

A novel class of discrete Fourier transform algorithms is presented. First, a new algorithm is presented for computing the DFT spectrum along any given direction. Then, computation of the entire DFT spectrum is computed using a minimal set of independent directions. It is shown that the new class of algorithms is both faster and more accurate than the traditional tensor decomposition of the DFT computation. Furthermore, the new algorithms allow for each direction to be computed independently of the others, hence allowing a parallel implementation.