A Fast Algorithm for the Evaluation of Legendre Expansions

An algorithm is presented for the rapid calculation of the values and coefficients of finite Legendre series. Given an n-term Legendre expansion, the algorithm produces its values at n Chebyshev nodes on the interval $[-1,1]$ for a cost proportional to $n\log n$. Similarly, given the valuesof a function f at n Chebyshev nodes, the algorithm produces the n-term Legendre expansion of the polynomial of degree $n - 1$ that is equal to f at these nodes. The cost of the algorithm is roughly three times that of the Fast Fourier Transform of length n, provided that calculations are performed to single precision accuracy. In double precision, the ratio is approximately 5.5. The method employed admits far-reaching generalizations and is currently being applied to several other problems.