Space-time trade-offs on the FFT algorithm

DOI10.1109/TIT.1978.1055938zbMath0379.65063OpenAlexW2134224523MaRDI QIDQ4158442

Sowmitri Swamy, John E. Savage

Publication date: 1978

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.1978.1055938

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items (17)

Space-time tradeoffs for linear recursion ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Time-space efficient algorithms for computing convolutions and related problems ⋮ Time-space tradeoffs for computing functions, using connectivity properties of their circuits ⋮ On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives ⋮ A space bound for one-tape multidimensional Turing machines ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Extreme time-space tradeoffs for graphs with small space requirements ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ On Reducing the Space Requirements of a Straight-Line Algorithm ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ A general class of resource tradeoffs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Size-space tradeoffs for oblivious computations ⋮ Lower bounds in algebraic computational complexity ⋮ The performance of multilective VLSI algorithms ⋮ Depth-Robust Graphs and Their Cumulative Memory Complexity

This page was built for publication: Space-time trade-offs on the FFT algorithm