Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms

DOI10.1137/0401003MaRDI QIDQ4729344zbMATH OpenOpenAlexFDO

Authors David A. Carlson

Publication date 1988

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0401003

zbMATH Keywords

computational complexitypolynomial multiplicationpebble gameembedded Fast Fourier transformstime-space trade offs

Mathematics Subject Classification ID

Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• Time and memory requirements of the nonequispaced FFT
• Improved upper complexity bounds for the discrete Fourier transform
• Fast algorithms for the computation of Fourier extensions of arbitrary length
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Faster homomorphic evaluation of discrete Fourier transforms
• A polymorphic radix-\(n\) framework for fast Fourier transforms
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• FAST FOURIER TRANSFORM ALGORITHM DESIGN AND TRADEOFFS ON THE CM-2
• scientific article; zbMATH DE number 60565

Cited in

(2)

• scientific article; zbMATH DE number 3940742 (Why is no real title available?)
• Time-space efficient algorithms for computing convolutions and related problems

This page was built for publication: Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729344)