Fast polynomial transform algorithms for digital convolution

DOI10.1109/TASSP.1980.1163372zbMath0524.65093OpenAlexW2031855568MaRDI QIDQ3036662

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 processingfast polynomial transformmultidimensional discrete Fourier transformdigital convolution

Mathematics Subject Classification ID

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

Related Items

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