# FPT - Fast polynomial transform

A **discrete polynomial transform (DPT)** is a generalisation of the discrete Fourier transform from the basis of complex exponentials \(\mathrm{e}^{\mathrm{i} k x}\) to arbitrary systems of algebraic polynomials satisfying a three-term recurrence relation. More precisely, let \(P_{0},P_{1},\dots:[-1,1]\rightarrow\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\). Typical examples are the classical orthogonal Jacobi polynomials \(P_{k}^{(\alpha,\beta)}\), which include the Legendre and Gegenbauer polynomials. Now, let \(f:[-1,1]\rightarrow\R\) be a polynomial of degree \(N\in\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), \] where the Chebyshev polnyomials of the first kind are defined by \[ T_k(x) = \cos(k\, \arccos x). \] A direct algorithm for computing this transformation needs \(\mathcal O(N^2)\) arithmetic operations. The FPT algorithm implemented in the NFFT library 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 \(\mathcal O(N \log^2 N)\) arithmetic operations.

The algorithms are implemented by Jens Keiner in `./kernel/fpt`

. The Matlab interface in `./matlab/fpt`

is implemented by Felix Bartel. Related papers are

- Potts, D., Steidl G., Tasche M.

**Fast algorithms for discrete polynomial transforms.**

Math. Comput. 67, 1577-1590, (full paper pdf), 1998

- Potts, D.

**Fast algorithms for discrete polynomial transforms on arbitrary grids.**

Linear Algebra Appl. 366, 353-370, (full paper pdf), 2001

- Keiner, J., Potts, D.

**Fast evaluation of quadrature formulae on the sphere.**

Math. Comput. 77, 397-419, (full paper pdf), 2008