A fast FFT-based discrete Legendre transform
This work provides a faster algorithm for a fundamental transform in numerical analysis, benefiting applications requiring Legendre transforms.
The paper presents an O(N(log N)^2 / log log N) algorithm for the discrete Legendre transform and its inverse, leveraging FFT-based methods. Numerical results demonstrate performance and accuracy.
An $\mathcal{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 $\mathcal{O}(N\log 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.