Jr. Driscoll et al., FAST DISCRETE POLYNOMIAL-TRANSFORMS WITH APPLICATIONS TO DATA-ANALYSIS FOR DISTANCE-TRANSITIVE GRAPHS, SIAM journal on computing, 26(4), 1997, pp. 1066-1099
Citations number
33
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Let P = {P-0,...,Pn-1) denote a set of polynomials with complex coeffi
cients. 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 disc
rete 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 fi
nd important applications in areas such as medical imaging and signal
processing. In this paper, we present fast algorithms for computing di
screte orthogonal polynomial transforms. For a system of N orthogonal
polynomials of degree at most N - 1, we give an O(N log(2) N) algorith
m for computing a discrete polynomial transform at an arbitrary set of
points instead of the N-2 operations required by direct evaluation. O
ur 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 orthogona
l polynomials generate the vector space of functions on a distance tra
nsitive graph. As a direct application of our work, we are able to giv
e a fast algorithm for computing subspace decompositions of this vecto
r space which respect the action of the symmetry group of such a graph
. This has direct applications to treating computational bottlenecks i
n the spectral analysis of data on distance transitive graphs, and we
discuss this in some detail.