A fast FFT-based discrete Legendre transform

DOI10.1093/IMANUM/DRV060MaRDI QIDQ4683735zbMATH OpenOpenAlexFDO

Authors Nicholas Hale, Alex Townsend

Publication date 26 September 2018

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00354

zbMATH Keywords

Chebyshev polynomialsdiscrete Legendre transformfast Fourier transformLegendre polynomials

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Special integral transforms (Legendre, Hilbert, etc.) (44A15) Numerical summation of series (65B10) Numerical methods for integral transforms (65R10) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: An $mathcalO(N(logN{)}^2/log!logN)$ algorithm for computing the discrete Legendre transform and its inverse is described. The algorithm combines a recently developed fast transform for converting between Legendre and Chebyshev coefficients with a Taylor series expansion for Chebyshev polynomials about equally-spaced points in the frequency domain. Both components are based on the FFT, and as an intermediate step we obtain an $mathcalO(NlogN)$ algorithm for evaluating a degree $N-1$ Chebyshev expansion at an $N$-point Legendre grid. Numerical results are given to demonstrate performance and accuracy.

Recommendations

• A Fast Algorithm for the Evaluation of Legendre Expansions
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula
• On the efficient parallel computation of Legendre transforms
• Fast algorithms for discrete polynomial transforms
• A fast and simple algorithm for the computation of Legendre coefficients

Cited in

(19)

• Stable extrapolation of analytic functions
• On the computation of discrete Legendre polynomial coefficients
• A pseudo-spectral Strang splitting method for linear dispersive problems with transparent boundary conditions
• Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation
• A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation
• Orthogonal polynomials on planar cubic curves
• On the efficient parallel computation of Legendre transforms
• On the stability of computing polynomial roots via confederate linearizations
• An algorithm for the convolution of Legendre series
• A Fast Algorithm for the Evaluation of Legendre Expansions
• scientific article; zbMATH DE number 1959453 (Why is no real title available?)
• On the use of Hahn's asymptotic formula and stabilized recurrence for a fast, simple and stable Chebyshev-Jacobi transform
• Fast polynomial transforms based on Toeplitz and Hankel matrices
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula
• A fast and simple algorithm for the computation of Legendre coefficients
• A faster multipole Legendre-Chebyshev transform
• High-order integration on regular triangulated manifolds reaches superalgebraic approximation rates through cubical reparametrizations
• On fast algorithms for the evaluation of Legendre coefficients

This page was built for publication: A fast FFT-based discrete Legendre transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4683735)