next up previous contents
Next: NFSFT - nonequispaced fast Up: Generalisations and inversion Previous: NSFFT - nonequispaced sparse   Contents


FPT - fast polynomial transform

A discrete polynomial transform (DPT) is a generalisation of the DFT from the basis of complex exponentials $ \mathrm{e}^{\mathrm{i} k x}$ to an arbitrary systems of algebraic polynomials satisfying a three-term recurrence relation. More precisely, let $ P_{0},P_{1},\hdots:[-1,1]\rightarrow\ensuremath{\mathbb{R}}$ be a sequence of polynomials that satisfies a three-term recurrence relation

$\displaystyle P_{k+1}(x) = (\alpha_{k} x + \beta_{k})P_{k}(x) + \gamma_{k} P_{k-1}(x),$    

with $ \alpha_{k} \neq 0$ , $ k\ge 0$ , $ P_{0}(x) := 1$ , and $ P_{-1}(x) := 0$ . Clearly, every $ P_{k}$ is a polynomial of exact degree $ k$ and typical examples are the classical orthogonal Jacobi polynomials $ P_{k}^{(\alpha,\beta)}$ .

Now, let $ f:[-1,1]\rightarrow\ensuremath{\mathbb{R}}$ be a polynomial of degree $ N\in\ensuremath{\mathbb{N}}$ given by the finite linear combination

$\displaystyle f(x) = \sum_{k=0}^{N} a_{k} P_{k}(x).$    

The discrete polynomial transform (DPT) and its fast version, the fast polynomial transform (FPT), are the transformation of the coefficients $ a_{k}$ into coefficients $ b_{k}$ from the orthogonal expansion of $ f$ into the basis of Chebyshev polynomials of the first kind $ T_{k}(x) := \cos(k
\arccos x)$ , i.e.,

$\displaystyle f(x) = \sum_{k=0}^N b_{k} T_{k}(x).$    

A direct algorithm for computing this transformation needs $ {\cal O}(N^2)$ arithmetic operations. The FPT algorithm implemented in the NFFT library follows the approach in [51] and is based on the idea of using the three-term-recurrence relation repeatedly. Together with a method for fast polynomial multiplication in the Chebyshev basis and a cascade-like summation process, this yields a method for computing the polynomial transform with $ {\cal O}(N \log^2 N)$ arithmetic operations. For more detailed information, we refer the reader to [12,13,51,44,32] and the references therein.


next up previous contents
Next: NFSFT - nonequispaced fast Up: Generalisations and inversion Previous: NSFFT - nonequispaced sparse   Contents
Jens Keiner 2006-11-20