Scalable Parallel Algorithms for Multidimensional Digital Signal Processing

摘要

A new algorithm for the multiprocessor computation of the multidimensionaldiscrete Fourier transform is presented. The algorithm eliminates the need for interprocessor communication and is highly scalable. The cost of eliminating interprocessor communication by this method is that one addition must be performed at each processing element for every input loaded into the machine. The algorithm is based on a new multidimensional discrete Fourier transform algorithm that computes a d-dimensional discrete Fourier transform by a set of independent k-dimensional discrete Fourier transforms (k