Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons

Open Access. Powered by Scholars. Published by Universities.®

Applied Mathematics

Dartmouth College

Series

Fast algorithm

Articles 1 - 1 of 1

Full-Text Articles in Theory and Algorithms

Fast Discrete Polynomial Transforms With Applications To Data Analysis For Distance Transitive Graphs, J. R. Driscoll, D. M. Healy, D. N. Rockmore Aug 1997

Fast Discrete Polynomial Transforms With Applications To Data Analysis For Distance Transitive Graphs, J. R. Driscoll, D. M. Healy, D. N. Rockmore

Dartmouth Scholarship

Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. 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 …