Fast algorithms for discrete polynomial transforms
From MaRDI portal
The authors consider the Vandermonde-like matrix \(P:=(P_k (\cos {j\pi \over N}))^N_{j, k=0}\), where the polynomials \(P_k\) satisfy a three-term recurrence relation. If \(P_k\) are the Chebyshev polynomials, then \(P\) coincides with \(C:= (\cos {jk\pi \over N})^N_{j,k =0}\). This paper presents a new fast algorithm for the computation of the matrix-vector product \(Pa\) in \(O(N \log^2N)\) arithmetical operations. The algorithm divides into a fast transform, which replaces \(Pa\) with \(C\widetilde a\), and a subsequent fast cosine transform. The first part of this algorithm is realized by a straightforward cascade summation based on properties of associated polynomials with respect to \(P_k\) and by fast polynomial multiplications. Numerical tests demonstrate that this fast polynomial transform realizes \(Pa\) with almost the same precision as the Clenshaw algorithm, but is much faster for \(N\geq 128\). This algorithm can be considered as a modified Driscoll-Healy algorithm [see \textit{J. R. Driscoll} and \textit{D. M. Healy}, Adv. Appl. Math. 15, 202-250 (1994; Zbl 0801.65141)].
Recommendations
- Fast algorithms for discrete polynomial transforms on arbitrary grids
- An extra-component method for evaluating fast matrix-vector multiplication with special functions
- Displacement-structure approach to polynomial Vandermonde and related matrices
- Fast algorithms with preprocessing for matrix-vector multiplication problems
- Fast summation based on fast trigonometric transforms at non‐equispaced nodes
- scientific article; zbMATH DE number 4005457
- Fast inversion of Vandermonde-like matrices involving orthogonal polynomials
- Fast methods for resumming matrix polynomials and Chebyshev matrix polynomials.
- A fast algorithm for evaluating the matrix polynomial I+A+. . .+A/sup N-1/
- On the normal matrix of the polynomial LS problem over the Chebyshev points
Cites work
- A Fast Algorithm for the Evaluation of Legendre Expansions
- A Polynomial Approach to Fast Algorithms for Discrete Fourier-Cosine and Fourier-Sine Transforms
- Computing Fourier transforms and convolutions on the 2-sphere
- Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
- Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
- Fast polynomial multiplication and convolutions related to the discrete cosine transform
- Fast radix-\(p\) discrete cosine transform
- Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials
- scientific article; zbMATH DE number 3864449 (Why is no real title available?)
- scientific article; zbMATH DE number 47594 (Why is no real title available?)
- scientific article; zbMATH DE number 3605240 (Why is no real title available?)
- scientific article; zbMATH DE number 3110365 (Why is no real title available?)
- On the associated orthogonal polynomials
- Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation
- The condition of Vandermonde-like matrices involving orthogonal polynomials
Cited in
(52)- A note on stability results for scattered data interpolation on Euclidean spheres
- A fast algorithm for nonequispaced Fourier transforms on the rotation group
- Fast conversion algorithms for orthogonal polynomials
- Recurrence relations and fast algorithms
- Fast discrete transforms by means of eigenpolynomials
- Fast algorithms for discrete Chebyshev-Vandermonde transforms and applications
- Fast spherical Fourier algorithms.
- Diagonalized Legendre spectral methods using Sobolev orthogonal polynomials for elliptic boundary value problems
- Fast algorithms for discrete polynomial transforms on arbitrary grids
- Local quadrature formulas on the sphere
- On expansions in orthogonal polynomials
- Fast SGL Fourier transforms for scattered data
- An algorithm for the rapid evaluation of special function transforms
- Quadrature in Besov spaces on the Euclidean sphere
- Polynomial operators and local approximation of solutions of pseudo-differential equations on the sphere
- Weighted quadrature formulas and approximation by zonal function networks on the sphere
- An alternative to Slepian functions on the unit sphere -- a space-frequency analysis based on localized spherical polynomials
- Fast algorithms for the multi-dimensional Jacobi polynomial transform
- Learning multivariate functions with low-dimensional structures using polynomial bases
- Fast associated classical orthogonal polynomial transforms
- An extra-component method for evaluating fast matrix-vector multiplication with special functions
- Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature
- On the efficient parallel computation of Legendre transforms
- Multidimensional polynomial transform algorithm for multidimensional discrete W transform
- A polynomial interpolation process at quasi-Chebyshev nodes with the FFT
- Reconstructing a function on the sphere from its means along vertical slices
- On the Numerical Solution of a Hypersingular Integral Equation with Fixed Singularities
- scientific article; zbMATH DE number 4100583 (Why is no real title available?)
- Sparse Legendre expansions via _1-minimization
- scientific article; zbMATH DE number 1247162 (Why is no real title available?)
- Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
- scientific article; zbMATH DE number 1959453 (Why is no real title available?)
- Orthogonal polynomial expansions on sparse grids
- A hybrid analytical-numerical technique for elliptic pdes
- Fast polynomial transforms based on Toeplitz and Hankel matrices
- A fast FFT-based discrete Legendre transform
- scientific article; zbMATH DE number 766215 (Why is no real title available?)
- Computing invariant sets of random differential equations using polynomial chaos
- A Polynomial Approach to Fast Algorithms for Discrete Fourier-Cosine and Fourier-Sine Transforms
- Polynomial processes for power prices
- Discrete transforms and orthogonal polynomials of (anti)symmetric multivariate cosine functions
- Fast evaluation of quadrature formulae on the sphere
- Scattered data approximation on the bisphere and application to texture analysis
- Sliced optimal transport on the sphere
- A fast and simple algorithm for the computation of Legendre coefficients
- The \(G\)-invariant graph Laplacian. I: Convergence rate and eigendecomposition.
- An adaptive orthogonal basis method for computing multiple solutions of differential equations with polynomial nonlinearities
- Fast polynomial multiplication and convolutions related to the discrete cosine transform
- On Volterra like integral equations coming from statistical process monitoring
- Uniform approximation on \([-1,1]\) via discrete de la Vallée Poussin means
- How well do fast discrete trigonometric transforms work for parametric numerical integration?
- Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice
This page was built for publication: Fast algorithms for discrete polynomial transforms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210958)
