Time-Space Tradeoffs on Back-to-Back FFT Algorithms
- 1 June 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 32 (6) , 585-589
- https://doi.org/10.1109/tc.1983.1676281
Abstract
This paper examines the performance of back-to-back applications of a fast Fourier transform algorithm with respect to computational time and space. Using a well-known pebble game as an analysis technique, a lower bound is derived on the product of time and space, which is of the form T · S = Ω(n2 log2n) for an n-input back-to-back FFT. The implications of this lower bound on applications of a back-to-back FFT circuit, such as polynomial multiplication and permutation graphs, are also discussed.Keywords
This publication has 9 references indexed in Scilit:
- Application of separability and independence notions for proving lower bounds of circuit complexityJournal of Mathematical Sciences, 1980
- Time-space tradeoffs for computing functions, using connectivity properties of their circuitsJournal of Computer and System Sciences, 1980
- Space-time trade-offs on the FFT algorithmIEEE Transactions on Information Theory, 1978
- Shifting Graphs and Their ApplicationsJournal of the ACM, 1976
- On non-linear lower bounds in computational complexityPublished by Association for Computing Machinery (ACM) ,1975
- Combinational complexity of some monotone functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- On Permutation Switching NetworksBell System Technical Journal, 1968
- A Permutation NetworkJournal of the ACM, 1968