Fast polynomial transform algorithms for digital convolution

DOI10.1109/TASSP.1980.1163372MaRDI QIDQ3036662zbMATH OpenOpenAlexFDO

Authors Henri J. Nussbaumer

Publication date 1980

Published in IEEE Transactions on Acoustics, Speech, and Signal Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tassp.1980.1163372

zbMATH Keywords

fast Fourier transformdigital signal processingmultidimensional discrete Fourier transformfast polynomial transformdigital convolution

Mathematics Subject Classification ID

Signal detection and filtering (aspects of stochastic processes) (60G35) Numerical methods for trigonometric approximation and interpolation (65T40) Trigonometric interpolation (42A15)

Cited in

(18)

• An efficient algorithm for cyclic convolution based on fast-polynomial and fast-\(W\) transforms
• On fast multiplication of polynomials over arbitrary algebras
• Exploring the advantages and challenges of Fermat NTT in FHE acceleration
• Detecting perfect powers in essentially linear time
• Special algorithms for convolutions over Galois fields
• Amortized bootstrapping revisited: simpler, asymptotically-faster, implemented
• On algorithms for digital signal processing of sequences
• When NTT meets Karatsuba: preprocess-then-NTT technique revisited
• A cache-friendly truncated FFT
• Integer multiplication in time \(O(n\log n)\)
• Irregular primes to 163 million
• Saber on ESP32
• Improved fast polynomial transform algorithm for cyclic convolutions
• HILA5: on reliability, reconciliation, and error correction for Ring LWE encryption
• Polynomial multiplication over finite fields in time \(O(n\log n)\)
• A Gröbner free alternative for polynomial system solving
• Faster polynomial multiplication via multipoint Kronecker substitution
• Fast systematic encoding of multiplicity codes

This page was built for publication: Fast polynomial transform algorithms for digital convolution

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