The Algebraic Approach to the Discrete Cosine and Sine Transforms and Their Fast Algorithms

DOI10.1137/S009753970139272XzbMath1046.42003MaRDI QIDQ4429686

José M. F. Moura, Markus Püschel

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

symmetryFFTgroup representationfast algorithmChebyshev polynomialdiscrete cosine transform (DCT)discrete Fourier transform (DFT)discrete sine transform (DST)polynomial transformalgebra representationdiscrete trigonometric transform (DTT)

Mathematics Subject Classification ID

Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Connections of hypergeometric functions with groups and algebras, and related topics (33C80) Numerical methods for discrete and fast Fourier transforms (65T50) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Applications of hypergeometric functions (33C90)

Related Items

Fast algorithms using orthogonal polynomials ⋮ On a constant-diagonals matrix ⋮ Spectral analysis of finite Markov chains with spherical symmetries ⋮ A Filon-type asymptotic approach to solving highly oscillatory second-order initial value problems ⋮ Radon transforms and lamplighter random walks ⋮ Factorizations and representations of the backward second-order linear recurrences ⋮ Symmetry-based matrix factorization ⋮ Harmonic analysis of finite lamplighter random walks ⋮ Signal Processing on Weighted Line Graphs ⋮ Some classes of tetradiagonal determinants via certain polynomial families ⋮ Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice ⋮ Lowest Complexity Self-Recursive Radix-2 DCT II/III Algorithms ⋮ Signal flow graph approach to efficient and forward stable DST algorithms ⋮ Improvement of the discrete cosine transform calculation by means of a recursive method ⋮ Fast and numerically stable algorithms for discrete cosine transforms ⋮ Recursive calculation of effective resistances in distance-regular networks based on Bose–Mesner algebra and Christoffel–Darboux identity ⋮ A sixth-order quasi-compact difference scheme for multidimensional Poisson equations without derivatives of source term

Uses Software

• AREP