Fast polynomial transforms based on Toeplitz and Hankel matrices
Alex Townsend, Marcus G. T. Webb, Sheehan Olver · Mathematics of Computation · 2017
Many standard conversion matrices between coefficients in classical orthogonal polynomial expansions can be decomposed using diagonally-scaled Hadamard products involving Toeplitz and Hankel matrices. This allows us to derive algorithms with an observed complexity of O ( N log 2 N ) \mathcal {O}(N\log ^2 \! N) , based on the fast Fourier transform, for converting coefficients of a degree N N polynomial in one polynomial basis to coefficients in another. Numerical results show that this approach is competitive with state-of-the-art techniques, requires no precomputational cost, can be implemented in a handful of lines of code, and is easily adapted to extended precision arithmetic.