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

DOI10.1137/0401003zbMATH Open0679.68073OpenAlexW1982322154MaRDI QIDQ4729344FDOQ4729344

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

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

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)

Cited In (2)

• Title not available (Why is that?)
• 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)