Computing with Expansions in Gegenbauer Polynomials

We develop fast algorithms for computations involving finite expansions in Gegenbauer polynomials. A method is described to convert any finite expansion between different families of Gegenbauer polynomials. For a degree-n expansion the computational cost is $\mathcal{O}(n(\log(1/\varepsilon)+|\alpha-\beta|))$, where $\varepsilon$ is the prescribed accuracy, and $\alpha$ and $\beta$ are the respective Gegenbauer indices. Special cases involving Chebyshev polynomials of first kind are particularly important. In combination with (nonequispaced) discrete cosine transforms, we obtain efficient methods for the evaluation of expansions at prescribed nodes, and for the projection onto a sequence of Gegenbauer polynomials from given function values, respectively.