Answers are grounded in this paper and cite their sources.
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 nlog 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.
No takes yet. Share an insight, caveat, or question.
Alpert et al. (1991) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: