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}kx}$ to arbitrary systems of algebraic polynomials satisfying a three-term recurrence relation. More precisely, let $P_0,P_1,\cdots :[-1,1]\to \text{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\ne 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]\to \text{R}$ be a polynomial of degree $N\in \text{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