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