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

digital convolutiondigital signal processingfast Fourier transformfast polynomial transformmultidimensional discrete Fourier transform

Mathematics Subject Classification ID

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

Cited in

(20)

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

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)