Title :
On the communication complexity of the discrete Fourier transform
Author_Institution :
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fDate :
6/1/1996 12:00:00 AM
Abstract :
The communication complexity of a linear transformation is the number of scalars which must be transferred between two processors, each of which holds half the input vector in order to perform the transformation such that each processor holds half the output vector. This letter shows that the communication complexity of the the discrete Fourier transform of size n is at most n/2. That is, given a suitable partition of the input and output vectors, only n/4 complex numbers must be sent in each direction. In contrast, fast Fourier transform (FFT) algorithms transfer at least n/2 complex numbers in each direction.
Keywords :
communication complexity; discrete Fourier transforms; parallel algorithms; signal processing; communication complexity; discrete Fourier transform; fast Fourier transform algorithms; input vector; linear transformation; output vector; parallel computer; scalars; Communication channels; Complexity theory; Concurrent computing; Discrete Fourier transforms; Distributed computing; Fast Fourier transforms; Matrix decomposition; Partitioning algorithms; Singular value decomposition; Vectors;
Journal_Title :
Signal Processing Letters, IEEE
