On the efficient parallel computation of Legendre transforms (Q2719280)

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.