Analogues of the fast Fourier transform: Fast special function transforms

This talk will survey efficient, numerically stable algorithms for the analysis and synthesis of linear combinations of special functions. These include algorithms both for computing the coefficients in linear combinations of the functions, given the values of these linear combinations at certain points, and, vice versa, for evaluating such linear combinations at those points, given the coefficients in the linear combinations. The costs of the algorithms for a linear combination of n functions are bounded by a constant times n ln(n) at any fixed precision; moreover, the constant is the same for all families of special functions satisfying three-term recurrence relations. The results will be illustrated via numerical examples.