Let P = {P-0,...,Pn-1) denote a set of polynomials with complex coefficients. Let 2 = (z(0),...,z(n-1)) subset of C denote any set of sample points. For any f = (f(0),..., f(n-1)) is an element of C-n, the discrete polynomial transform of f (with respect to P and Z) is defined as the collection of sums, {(f) over cap(P-0),..., (f) over cap(Pn-1)}, where (f) over cap(P-j) = [f, P-j] = Sigma(i=0)(n-1) f(i)P(j)(z(i))w(i) for some associated weight function to. These sorts of transforms find important applications in areas such as medical imaging and signal processing. In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system of N orthogonal polynomials of degree at most N - 1, we give an O(N log(2) N) algorithm for computing a discrete polynomial transform at an arbitrary set of points instead of the N-2 operations required by direct evaluation. Our algorithm depends only on the fact that orthogonal polynomial sets satisfy a three-term recurrence and thus it may be applied to any such set of discretely sampled functions. In particular, sampled orthogonal polynomials generate the vector space of functions on a distance transitive graph. As a direct application of our work, we are able to give a fast algorithm for computing subspace decompositions of this vector space which respect the action of the symmetry group of such a graph. This has direct applications to treating computational bottlenecks in the spectral analysis of data on distance transitive graphs, and we discuss this in some detail.
