2015/05/02 by Nicholas Hale, Alex Townsend, Hale, Nicholas +1
Computer Science · #Digital Filter Design and Implementation #FOS: Mathematics #Image and Signal Denoising Methods #Numerical Analysis (math.NA) #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.1505.00354
openalex publication_date 2015/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An O(N(log N)2/log log N) algorithm for computing the discrete Legendre transform and its inverse is described. The algorithm combines a recently developed fast transform for converting between Legendre and Chebyshev coefficients with a Taylor series expansion for Chebyshev polynomials about equally-spaced points in the frequency domain. Both components are based on the FFT, and as an intermediate step we obtain an O(Nlog N) algorithm for evaluating a degree N-1 Chebyshev expansion at an N-point Legendre grid. Numerical results are given to demonstrate performance and accuracy.