Time-space efficient algorithms for computing convolutions and related problems

DOI10.1016/0890-5401(87)90060-5zbMath0636.68036OpenAlexW2042521895MaRDI QIDQ1098288

David A. Carlson

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90060-5

zbMATH Keywords

convolutionfast Fourier transformpolynomial multiplicationpebble game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Fast multiplication of large numbers
• Time-Space trade-offs for some algebraic problems
• Time-Space Tradeoffs on Back-to-Back FFT Algorithms
• Space-time trade-offs on the FFT algorithm

This page was built for publication: Time-space efficient algorithms for computing convolutions and related problems