Recurrence relations and fast algorithms

DOI10.1016/J.ACHA.2009.07.005MaRDI QIDQ1045714zbMATH OpenOpenAlexFDO

Authors Mark Tygert

Publication date 15 December 2009

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.acha.2009.07.005

zbMATH Keywords

fast algorithmspseudospectralrecurrence relationsspecial functionstransforms

Mathematics Subject Classification ID

Numerical approximation and evaluation of special functions (33F05) Computation of special functions and constants, construction of tables (65D20) Numerical aspects of recurrence relations (65Q30)

Review text

Faster algorithms are constructed for evaluating transforms associated with families of functions which satisfy recurrence relations. The algorithms are efficient in the sense that their computation costs are proportional to \(n\ln n\) at any fixed precision of computations, where \(n\) is the amount of input and output data.

Recommendations

• An algorithm for the rapid evaluation of special function transforms
• scientific article; zbMATH DE number 4100583
• Fast algorithms for discrete polynomial transforms
• An Efficient Formula for Linear Recurrences
• Singular integral transforms and fast numerical algorithms

Cites work

• A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
• A Fast Algorithm for the Calculation of the Roots of Special Functions
• A fast spherical filter with uniform resolution
• A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
• Calculation of Gauss Quadrature Rules
• Fast Algorithms for Spherical Harmonic Expansions
• Fast algorithms for spherical harmonic expansions. II.
• scientific article; zbMATH DE number 3172037 (Why is no real title available?)
• scientific article; zbMATH DE number 274379 (Why is no real title available?)
• Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory
• Recurrence relations and fast algorithms

Cited in

(13)

• Recurrence relations and fast algorithms
• An algorithm for finding recurrence relations of binomial sums and its complexity
• Fast recurrence relation for computer-generated-hologram
• Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation
• An algorithm for the rapid evaluation of special function transforms
• An extra-component method for evaluating fast matrix-vector multiplication with special functions
• A Hermite-based shallow water solver for a thin ``ocean over a rotating sphere
• scientific article; zbMATH DE number 4007552 (Why is no real title available?)
• scientific article; zbMATH DE number 1263421 (Why is no real title available?)
• Revisiting the concentration problem of vector fields within a spherical cap: a commuting differential operator solution
• SuperDC: superfast divide-and-conquer eigenvalue decomposition with improved stability for rank-structured matrices
• Steerable principal components for space-frequency localized images
• Fast algorithms using orthogonal polynomials

Describes a project that uses

Uses Software

• FFTW

This page was built for publication: Recurrence relations and fast algorithms

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