Add Fourier--Legendre transform about fasttransforms.jl HOT 4 OPEN

What about this?

FOURIER -> LEGENDRE:
One can evaluation an n-degree Fourier expansion at n evaluation points in O(n log n) operations. One can pick a Chebyshev grid as the evaluation points and then do a fast cheb2leg transform.

LEGENDRE -> FOURIER:
A little more difficult, but one can evaluate an n-degree Legendre expansion at n equispaced points in O(n log n) operations. This will require a little more work on an NDCT. Then, do an IFFT for the Fourier coefficients.

With the oversampling of m = O(n^2), I suspect that one can do the transform in at most O(m log m).

from fasttransforms.jl.

As far as I know, what's special about the Adcock-Hansen method is that the conversion assimilates the convergence properties of the new Hilbert space.

If I take the Fourier expansion coefficients of e^x, on [0,2pi), then it will not converge uniformly due to the Gibbs phenomenon. But the Adcock-Hansen method uses the (condition number approximately 1, rectangular) matrix of connection coefficients to convert to a Legendre expansion that is supposed to converge in L² and uniformly.

The stringent requirement is exact Fourier expansion coefficients, though, since Fourier interpolant coefficients are subject to aliasing.

from fasttransforms.jl.

To be honest, I haven't seriously looked at adding this, it's just on the wish list. Maybe the oversampling is enough to resolve Gibbs, and then your proposal would be faster!

from fasttransforms.jl.

No, you're right. I forgot about Gibbs issues. You need something like least squares.

I derived a fast(er) algorithm for least squares with Chebyshev in Section 7 of https://arxiv.org/pdf/1605.09601.pdf. This is probably useful if you go ahead.

from fasttransforms.jl.