Fast transform algorithm for legendre polynomial transforms

Abstract

Let P={p0,p1,...,pn-1] denote the collection of the first n Legendre polynomials pk of degree k and let X={x0,x1,...,xn-1} be a set of n sample points. The Discrete Legendre polynomial transform (DLT) of an input vector,f=(f0,f1,...,fn-1)of size n is defined by {L(0),L(1),...L(n-1)},where L(l)= for each j=0,1,...,n-1. For the given collection of n Legendre polynomials, the straightforward method for computing DLT requires an O(n3) computational cost. This cost gets prohibitively increased for large values of n and hence it is too much for practical purpose. This paper describes an algorithm for fast computation of DLTs. The fast algorithm computes the DLT of any input vector of size non a set of n arbitrary sample points in an O((nlog2n)2) cost of complexity. The numerical experiments carried out demonstrate that the fast algorithm is faster than the straightforward algorithm when n>128.