The expansion in Gegenbauer polynomials: a simple method for the fast computation of the Gegenbauer coefficients

We present a simple and fast algorithm for the computation of the Gegenbauer transform, which is known to be very useful in the development of spectral methods for the numerical solution of ordinary and partial differential equations of physical interest. We prove that the coefficients of the expansion of a function f(x) in Gegenbauer (also known as ultraspherical) polynomials coincide with the Fourier coefficients of a suitable integral transform of the function f(x). This allows to compute N Gegenbauer coefficients in O(N log_2 N) operations by means of a single Fast Fourier Transform of the integral transform of f(x). We also show that the inverse Gegenbauer transform is expressible as the Abel-type transform of a suitable Fourier series. This fact produces a novel algorithm for the fast evaluation of Gegenbauer expansions.