Contribution in edited book
Efficient computation of Chebyshev polynomials
Publication Details
Book title:  Computer Algebra Systems: A Practical Guide

Abstract
Orthogonal polynomials can be calculated by computation of determinants, by the use of generating functions, in terms of Rodrigues formulas, by iterating recurrence equations, calculating the polynomial solutions of differential equations, through closed form representations and by other means. In computer algebra systems all these methods can be implemented. Depending on the application one might need 1. one (or many) of these polynomials in any form or specifically inexpanded form,2. the exact rational value of one of these polynomials at a certain rationalpoint,3. or a decimal approximation of the value of one of these polynomials ata certain point.In this article, we give an overview about the efficiency of the above methods in the general purpose computer algebra systems Axiom, Macsyma, Maple, Mathematica, MuPAD and REDUCE. Primarily we study the implementation of the Chebyshev polynomials of the first kind as an example case. First, we consider the builtin implementations of the Chebyshev polynomials in these systems. Next we study the classical algorithms beginning with the slow ones, and leading to the efficient ones. Finally, we finish with an algorithm based on a divide and conquer approach which has a remarkable complexity. In particular, we will show that· to obtain the expanded form of one of the Chebyshev polynomials (this is how the output is given by all the builtin commands), an iterative use of its power series representation is most efficient; the same argument applies to other classical systems of orthogonal polynomials; this is almost trivial because the classical orthogonal polynomials form hypergeometric series, but only Mathematica uses this approach;· for numerical purposes (mainly rationally exact, but also decimal approximation), a divide and conquer approach that is available forChebyshev polynomials is much preferable. This approach, however, is not efficient if the expanded form of the polynomial is needed.We present all algorithms as short programs. In each case, we choose the language with the best "asymptotic performance". This code should show that we tried to implement in as straightforward a manner as possible.