On the communication complexity of the discrete Fourier transform

Author

Toledo, Sivan

Author_Institution

Lab. for Comput. Sci., MIT, Cambridge, MA, USA

Volume

3

Issue

6

fYear

1996

fDate

6/1/1996 12:00:00 AM

Firstpage

171

Lastpage

172

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;

fLanguage

English

Journal_Title

Signal Processing Letters, IEEE

Publisher

ieee

ISSN

1070-9908

Type

jour

DOI

10.1109/97.503280

Filename

503280