Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs

DOI10.1137/S0097539792240121zbMath0896.65094OpenAlexW2149599446MaRDI QIDQ4376166

Daniel N. Rockmore, Dennis M. jun. Healy, James R. Driscoll

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792240121

zbMATH Keywords

orthogonal polynomialsFFTfast Fourier transformfast algorithmdistance transitive graphthree-term recurrencediscrete polynomial transform

Mathematics Subject Classification ID

Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Numerical methods for discrete and fast Fourier transforms (65T50) Distance in graphs (05C12) Software, source code, etc. for problems pertaining to harmonic analysis on Euclidean spaces (42-04)

Related Items

Fast algorithms for discrete polynomial transforms on arbitrary grids, Fast algorithms using orthogonal polynomials, A fast Hermite transform, A Hermite pseudospectral solver for two-dimensional incompressible flows on infinite domains, Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations, Sparse Legendre expansions via \(\ell_1\)-minimization, Fast SGL Fourier transforms for scattered data, Fast spherical Fourier algorithms., Fast Fourier Transforms for Spherical Gauss-Laguerre Basis Functions, Orthogonal polynomial expansions on sparse grids, Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice, Spectral radial basis functions for full sphere computations, FFTs on the rotation group, EXCHANGEABLE PAIRS OF BERNOULLI RANDOM VARIABLES, KRAWTCHOUCK POLYNOMIALS, AND EHRENFEST URNS, A note on stability results for scattered data interpolation on Euclidean spheres, Efficient computation of Fourier transforms on compact groups, Nonreflecting boundary conditions for elastodynamic scattering, Fast algorithms for discrete polynomial transforms, Fast conversion algorithms for orthogonal polynomials, Double coset decompositions and computational harmonic analysis on groups, Computation of far-field solutions based on exact nonreflecting boundary conditions for the time-dependent wave equation, Algorithms for fast convolutions on motion groups, Developement of a Numerical Procedure for Direct Simulations of Turbulent Convection in a Closed Rectangular Cell, Computational harmonic analysis for tensor fields on the two-sphere, Fast and stable algorithms for discrete spherical Fourier transforms, Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation