On the efficient parallel computation of Legendre transforms
type: Item
instance of: scholarly article
zbMATH Open document ID: 0995.65149
DOI: 10.1137/S1064827599355864
author: Márcia A. Inda
author: R. H. Bisseling
author: David K. Maslen
published in: SIAM Journal on Scientific Computing
publication date: 2001-06-21T00:00:00Z
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 42C15
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 1608939
zbMATH Keywords: orthogonal polynomials
zbMATH Keywords: Legendre polynomials
zbMATH Keywords: BSP
zbMATH Keywords: parallel computation
zbMATH Keywords: computational harmonic analysis
zbMATH Keywords: numerical examples
zbMATH Keywords: Chebyshev polynomial
zbMATH Keywords: recurrence relation
zbMATH Keywords: divide-and-conquer strategy
zbMATH Keywords: fast Chebyshev transform
zbMATH Keywords: fast cosine transform
describes a project that uses: BSPlib
MaRDI profile type: Publication
full work available at URL: s1064827599355864
OpenAlex ID: W2134865908
title: On the efficient parallel computation of Legendre transforms
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.
reviewed by: Adhemar Bultheel
description: scientific article; zbMATH DE number 1608939