Nonequispaced fast Fourier transform
Polynomials

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