On the efficient parallel computation of legendre transforms

In this article, we discuss a parallel implementation of efficient algorith ms for computation of Legendre polynomial transforms and other orthogonal p olynomial transforms. We develop an approach to the Driscoll-Healy algorith m using polynomial arithmetic and present experimental results on the accur acy, efficiency, and scalability of our implementation. The algorithms were implemented in ANSI C using the BSPlib communications library. We also pre sent a new algorithm for computing the cosine transform of two vectors at t he same time.