Fast polynomial transforms based on Toeplitz and Hankel matrices

DOI10.1090/MCOM/3277zbMATH Open1478.65147arXiv1604.07486OpenAlexW2964132515MaRDI QIDQ4637582FDOQ4637582

Authors: Alex Townsend, Marcus Webb, Sheehan Olver 

Publication date: 24 April 2018

Published in: Mathematics of Computation (Search for Journal in Brave)

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 $smashmathcalO(N(logN{)}^2)$ algorithms, 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.

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

Recommendations

• Fast conversion algorithms for orthogonal polynomials
• scientific article; zbMATH DE number 7709336
• Fast algorithms for discrete polynomial transforms
• Fast associated classical orthogonal polynomial transforms
• scientific article; zbMATH DE number 1617990

zbMATH Keywords

Legendre polynomialsChebyshev polynomialsfast Fourier transformorthogonal polynomialsconversion matrixpolynomial basis conversionfast polynomial transformsToeplitz-dot-Hankel matrix

Mathematics Subject Classification ID

Toeplitz, Cauchy, and related matrices (15B05) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• Julia: a fresh approach to numerical computing
• NIST handbook of mathematical functions
• On the low-rank approximation by the pivoted Cholesky decomposition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation theory and approximation practice
• Title not available (Why is that?)
• Efficient Spectral-Galerkin Method I. Direct Solvers of Second- and Fourth-Order Equations Using Legendre Polynomials
• Rapid Computation of the Discrete Fourier Transform
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• A fast and well-conditioned spectral method
• Title not available (Why is that?)
• Connection coefficients between orthogonal polynomials and the canonical sequence: An approach based on symbolic computation
• Title not available (Why is that?)
• Some connection and linearization problems for polynomials in and beyond the Askey scheme
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula
• Title not available (Why is that?)
• A fast and simple algorithm for the computation of Legendre coefficients
• Fast algorithms for discrete polynomial transforms
• A Fast Algorithm for the Evaluation of Legendre Expansions
• Implementing Clenshaw-Curtis quadrature, I methodology and experience
• The Chebyshev–Legendre Method: Implementing Legendre Methods on Chebyshev Points
• A fast symmetric SVD algorithm for square Hankel matrices
• Fast evaluation of real and complex exponential sums
• Computing with expansions in Gegenbauer polynomials
• Continuous analogues of matrix factorizations
• An algorithm for the convolution of Legendre series
• How to choose modified moments?
• Title not available (Why is that?)
• A fast FFT-based discrete Legendre transform
• On the singular values of matrices with displacement structure
• Strong rank revealing Cholesky factorization
• On rapid computation of expansions in ultraspherical polynomials
• On the use of Hahn's asymptotic formula and stabilized recurrence for a fast, simple and stable Chebyshev-Jacobi transform

Cited In (32)

• Pricing European-type, early-exercise and discrete barrier options using an algorithm for the convolution of Legendre series
• Polynomial (chaos) approximation of maximum eigenvalue functions. Efficiency and limitations
• An iterative domain decomposition, spectral finite element method on non-conforming meshes suitable for high frequency Helmholtz problems
• Fast algorithms for the multi-dimensional Jacobi polynomial transform
• Fast associated classical orthogonal polynomial transforms
• Weakly regular Sturm-Liouville problems: a corrected spectral matrix method
• A new Legendre polynomial-based approach for non-autonomous linear ODEs
• Sobolev‐orthogonal systems with tridiagonal skew‐Hermitian differentiation matrices
• Non-homogeneous wave equation on a cone
• Optimal error estimates of spectral Galerkin method for mixed diffusion equations
• Computationally Efficient Reduced Polynomial Based Algorithms for Hermitian Toeplitz Matrices
• Optimal regularity and error estimates of a spectral Galerkin method for fractional advection-diffusion-reaction equations
• On the singular values of matrices with displacement structure
• How much faster does the best polynomial approximation converge than Legendre projection?
• Correlators of polynomial processes
• Computing with functions in the ball
• A fast and spectrally convergent algorithm for rational-order fractional integral and differential equations
• Fast transforms of Toeplitz matrices
• A spectral Galerkin approximation of optimal control problem governed by fractional advection-diffusion-reaction equations
• Piecewise nonlinear approximation for non-smooth functions
• Fast discrete transforms by means of eigenpolynomials
• Computing equilibrium measures with power law kernels
• Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons
• Fast algorithms using orthogonal polynomials
• Fast structured Jacobi-Jacobi transforms
• Sharp error estimates of a spectral Galerkin method for a diffusion-reaction equation with integral fractional Laplacian on a disk
• A faster multipole Legendre-Chebyshev transform
• On spectral Petrov-Galerkin method for solving optimal control problem governed by a two-sided fractional diffusion equation
• Fast spectral Petrov-Galerkin method for fractional elliptic equations
• Orthogonal polynomials in and on a quadratic surface of revolution
• A nonuniform fast Fourier transform based on low rank approximation
• Bounds on the singular values of matrices with displacement structure

Uses Software

• Digital Library of Mathematical Functions
• FFTW
• Chebfun
• Clenshaw-Curtis
• Julia
• ApproxFun
• FastTransforms.jl
• GitHub

This page was built for publication: Fast polynomial transforms based on Toeplitz and Hankel matrices

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