A Fast Algorithm for the Evaluation of Legendre Expansions

Abstract

An algorithm is presented for a rapid calculation of the values and coefficients of finite Legendre series. Given an n-term Legendre expansion, the algorithm produces its values at n Chebyshev nodes on the interval -1,1 for a cost proportional to n log n. Similarly, given the values of a function f at n Chebyshev nodes, the algorithm produces the n-term Legendre expansion of the polynomial of degree n - 1 that is equal of f at these nodes. The cost of the algorithm is roughly 3 times that of the fast Fourier transform of length n, provided that calculations are performed to single precision accuracy. In double precision, the ratio is approximately 5.5. The method employed admits far-reaching generalizations and is currently being applied to several other problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA206625

Entities

People

  • B. Alpert
  • Vladimir Rokhlin

Organizations

  • Yale University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Analytic Functions
  • Applied Mathematics
  • Arithmetic
  • Chebyshev Approximations
  • Chebyshev Polynomials
  • Computations
  • Differential Equations
  • Equations
  • Fast Fourier Transforms
  • Integrals
  • Numbers
  • Partial Differential Equations
  • Polynomials
  • Precision
  • Theorems

Fields of Study

  • Computer science

Readers

  • Analytical Mechanics
  • Calculus or Mathematical Analysis
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)