A fast FFT-based discrete Legendre transform

Nicholas Hale, Alex Townsend

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 tr…