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 threeterm recurrence relation. More precisely, let \(P_{0},P_{1},\dots:[1,1]\rightarrow\R\) be a sequence of polynomials that satisfies a threeterm recurrence relation \[ P_{k+1}(x) = (\alpha_{k} x + \beta_{k})P_{k}(x) + \gamma_{k} P_{k1}(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 threetermrecurrence relation repeatedly. Together with a method for fast polynomial multiplication in the Chebyshev basis and a cascadelike 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, 15771590, (full paper pdf), 1998

Potts, D.
Fast algorithms for discrete polynomial transforms on arbitrary grids.
Linear Algebra Appl. 366, 353370, (full paper pdf), 2001
 Keiner, J., Potts, D.
Fast evaluation of quadrature formulae on the sphere.
Math. Comput. 77, 397419, (full paper pdf), 2008