A Fast, Simple, and Stable Chebyshev--Legendre Transform Using an Asymptotic Formula

Nicholas Hale, Alex Townsend

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


A fast, simple, and numerically stable transform for converting between Legendre and Chebyshev coefficients of a degree N polynomial in O(N(log N)2/ log log N) operations is derived. The fundamental idea of the algorithm is to rewrite a well-known asymptotic formula for Legendre polynomials of large degree as a weighted linear combination of Chebyshev polynomials, which can then be evaluated by using the discrete cosine transform. Numerical results are provided to demonstrate the efficiency and numerical stability. Since the algorithm evaluates a Legendre expansion at an N +1 Chebyshev grid as an intermediate step, it also provides a fast transform between Legendre coefficients and values on a Chebyshev grid. © 2014 Society for Industrial and Applied Mathematics.
Original languageEnglish (US)
Pages (from-to)A148-A167
Number of pages1
JournalSIAM Journal on Scientific Computing
Issue number1
StatePublished - Feb 6 2014
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUK-C1-013-04
Acknowledgements: The first author's work was supported by The MathWorks, Inc., and King Abdullah University of Science and Technology (KAUST), award KUK-C1-013-04. The second author's work was supported by EPSRC grant EP/P505666/1 and by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement 291068.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'A Fast, Simple, and Stable Chebyshev--Legendre Transform Using an Asymptotic Formula'. Together they form a unique fingerprint.

Cite this