Space-time trade-offs on the FFT algorithm

Author

Savage, John E. ; Swamy, Sowmitri

Volume

Issue

fYear

1978

fDate

9/1/1978 12:00:00 AM

Firstpage

563

Lastpage

568

Abstract

The performance of the fast Fourier transfmm algorithm is examined under limitations on computational space and time. It is shown that if the algorithm with $n$ inputs, $n$ as a power of two, is implemented with $S$ temporary locations where $S=o(n/ \\log n)$ , then the computation time $T$ grows faster than $n \\log n$ . Furthermore, $T$ can grow as fast as $n^{2}$ if $S=S_{\\min} + O(1)$ where $S_{\\min}=l+\\log _{2}n$ , the minimum necessary. These results are obtained by deriving tight bounds on $T$ versus $S$ and $n$ .

Keywords

DFT; Discrete Fourier transforms (DFT´s); Graph theory; Algorithm design and analysis; Batteries; Computer science; Discrete Fourier transforms; Extraterrestrial measurements; Fast Fourier transforms; Helium; History; Signal processing algorithms; Time measurement;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1978.1055938

Filename

1055938

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=929076