Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Fast polynomial transforms based on Toeplitz and Hankel matrices


Authors: Alex Townsend, Marcus Webb and Sheehan Olver
Journal: Math. Comp. 87 (2018), 1913-1934
MSC (2010): Primary 65T50, 65D05, 15B05
DOI: https://doi.org/10.1090/mcom/3277
Published electronically: November 6, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \smash {\mathcal {O}(N\log ^2 \! N)}$, based on the fast Fourier transform, for converting coefficients of a degree $ 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65T50, 65D05, 15B05

Retrieve articles in all journals with MSC (2010): 65T50, 65D05, 15B05


Additional Information

Alex Townsend
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: townsend@cornell.edu

Marcus Webb
Affiliation: Department of Computer Science, KU Leuven, 3001 Leuven, Belgium
Email: marcus.webb@cs.kuleuven.be

Sheehan Olver
Affiliation: Department of Mathematics, Imperial College, London SW7 2AZ, United Kingdom
Email: s.olver@imperial.ac.uk

DOI: https://doi.org/10.1090/mcom/3277
Keywords: Conversion matrix, Toeplitz, Hankel, Hadamard product
Received by editor(s): May 10, 2016
Received by editor(s) in revised form: November 20, 2016, and March 9, 2017
Published electronically: November 6, 2017
Additional Notes: The work of the first author was supported by the National Science Foundation grant No. 1522577
The work of the second author was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/H023348/1 for the University of Cambridge Centre for Doctoral Training, the Cambridge Centre for Analysis, and the London Mathematical Society Cecil King Travel Scholarship 2015
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society