On the efficient parallel computation of Legendre transforms

DOI10.1137/S1064827599355864MaRDI QIDQ2719280zbMATH OpenOpenAlexFDO

Authors Márcia A. Inda, R. H. Bisseling, David K. Maslen

Publication date 21 June 2001

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

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

zbMATH Keywords

BSPChebyshev polynomialcomputational harmonic analysisdivide-and-conquer strategyfast Chebyshev transformfast cosine transformLegendre polynomialsnumerical examplesorthogonal polynomialsparallel computationrecurrence relation

Mathematics Subject Classification ID

General harmonic expansions, frames (42C15) Numerical methods for discrete and fast Fourier transforms (65T50) Parallel numerical computation (65Y05)

Review text

The algorithm of \textit{J. R. Driscoll, D.M. Healy jun.} and \textit{J. R. Driscoll, D.M. Healy jun.} and \textit{J. R. Driscoll, D.M. Healy jun.} and \textit{D. N. Rockmore} [SIAM J. Comput. 26, No.~4, 1066-1099 (1997; Zbl 0896.65094)] for discrete Legendre transformation is a fast algorithm of \(O(N \log^2 N)\) operations. The core of the algorithm is based on the special case where the sample points are the zeros of the Chebyshev polynomial. This allows to compute the product \(f p_l\), evaluated in the sample points very efficiently. \(f\) is the given function to be transformed and \(p_l\) is the \(l\)-th orthogonal polynomial in a general discrete polynomial transform. The recurrence relation and a divide-and-conquer strategy lead to a fast algorithm.NEWLINENEWLINENEWLINEThis paper analyses a parallel implementation in great detail. This includes versions of the fast Chebyshev transform and the computation of a fast cosine transform of two vectors simultaneously. Accuracy, efficiency and scalability are analysed and experimentally verified.

Recommendations

• A fast FFT-based discrete Legendre transform
• \(\mathcal{O}(1)\) computation of Legendre polynomials and Gauss-Legendre nodes and weights for parallel computing
• Fast algorithms for discrete polynomial transforms
• A fast and simple algorithm for the computation of Legendre coefficients
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula

Cited in

(6)

• A fast Legendre transform algorithm and applications to the adhesion model
• \(\mathcal{O}(1)\) computation of Legendre polynomials and Gauss-Legendre nodes and weights for parallel computing
• A fast FFT-based discrete Legendre transform
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula
• Minimizing Communication in the Multidimensional FFT
• A faster multipole Legendre-Chebyshev transform

Describes a project that uses

Uses Software

• BSPlib

This page was built for publication: On the efficient parallel computation of Legendre transforms

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