ON THE COMMUNICATION COMPLEXITY OF THE DISCRETE FOURIER-TRANSFORM

The communication complexity of a linear transformation is the number of scalars which must be transferred between two processors, each of w hich holds half the input vector in order to perform the transformatio n such that each processor holds half the output vector, This letter s hows that the communication complexity of the the discrete Fourier tra nsform of size n is at most n/2, That is, given a suitable partition o f the input and output vectors, only n/4 complex numbers must be sent in each direction. In contrast, fast Fourier transform (FFT) algorithm s transfer at least n/2 complex numbers in each direction.