Fachbereich Mathematik, Universität Rostock, D--18051 Rostock ; Fakultät für Mathematik und Informatik, Universität Mannheim, D--68131 Mannheim ; Fachbereich Mathematik, Universität Rostock, D--18051 Rostock
Abstract:
Consider the Vandermonde-like matrix , where the polynomials satisfy a three-term recurrence relation. If are the Chebyshev polynomials , then coincides with . This paper presents a new fast algorithm for the computation of the matrix-vector product in arithmetical operations. The algorithm divides into a fast transform which replaces with and a subsequent fast cosine transform. The first and central part of the algorithm is realized by a straightforward cascade summation based on properties of associated polynomials and by fast polynomial multiplications. Numerical tests demonstrate that our fast polynomial transform realizes with almost the same precision as the Clenshaw algorithm, but is much faster for .