New algorithms for digital convolution

DOI10.1109/TASSP.1977.1162981MaRDI QIDQ3048190zbMATH OpenFDO

Authors Ramesh C. Agarwal, James W. Cooley

Publication date 1977

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.1977.1162981

zbMATH Keywords

cyclic convolutionfast Fourier transformnumber-theoretic transforms

Mathematics Subject Classification ID

Congruences; primitive roots; residue systems (11A07) Trigonometric approximation (42A10) Convolution, factorization for one variable harmonic analysis (42A85) Numerical methods for trigonometric approximation and interpolation (65T40)

Cited in

(15)

• Index transforms for multidimensional DFT's and convolutions
• Numerical Fourier and Bessel transforms in logarithmic variables
• Matrix displacement decompositions and applications to Toeplitz linear systems
• Matrix decompositions using displacement rank and classes of commutative matrix algebras
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Fast computation of convolution operations via low-rank approximation
• Fast, prime factor, discrete Fourier transform algorithms over \(\text{GF}(2^m)\) for \(8 \leqslant m \leqslant 10\)
• Integer multiplication in time \(O(n\log n)\)
• Polynomial multiplication over finite fields in time O(n n)
• Derivation and analysis of fast bilinear algorithms for convolution
• Multiplication
• Realization of discrete Fourier transforms using a nesting algorithm
• Automatic derivation and implementation of fast convolution algorithms
• Communication lower bounds for nested bilinear algorithms via rank expansion of Kronecker products
• Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields

This page was built for publication: New algorithms for digital convolution

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