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

$$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

$$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.,

$$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.