Fast Fourier transforms of piecewise polynomials

We introduce an efficient algorithm for evaluating the Fourier transform of piecewise-polynomial data on d-dimensional simplices in D-dimensional Euclidean space RD. It generalizes butterfly algorithms for pointwise (d=0) nonuniform fast Fourier transforms, with new dimensional recurrences for exponential-polynomial moments. Error analysis and numerical comparisons with direct evaluation validate the efficiency and accuracy of the algorithm.