# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## Fast algorithms for discrete polynomial transformsHTML articles powered by AMS MathViewer

by Daniel Potts, Gabriele Steidl and Manfred Tasche
Math. Comp. 67 (1998), 1577-1590 Request permission

## Abstract:

Consider the Vandermonde-like matrix ${\mathbf {P}}:=(P_k(\cos \frac {j\pi }{N}))_{j,k=0}^N$, where the polynomials $P_k$ satisfy a three-term recurrence relation. If $P_k$ are the Chebyshev polynomials $T_k$, then ${\mathbf {P}}$ coincides with ${\mathbf {C}}_{N+1}:= (\cos \frac {jk\pi }{N})_{j,k=0}^N$. This paper presents a new fast algorithm for the computation of the matrix-vector product ${\mathbf {Pa}}$ in $O(N \log ^2N)$ arithmetical operations. The algorithm divides into a fast transform which replaces ${\mathbf {Pa}}$ with ${\mathbf {C}}_{N+1} {\mathbf {\tilde a}}$ 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 ${\mathbf {Pa}}$ with almost the same precision as the Clenshaw algorithm, but is much faster for $N\ge 128$.
Similar Articles
• Retrieve articles in Mathematics of Computation with MSC (1991): 65T99, 42C10, 33C25
• Retrieve articles in all journals with MSC (1991): 65T99, 42C10, 33C25
• Daniel Potts
• Affiliation: Fachbereich Mathematik, Universität Rostock, D–18051 Rostock
• Email: daniel.potts@stud.uni-rostock.de
• Gabriele Steidl
• Affiliation: Fakultät für Mathematik und Informatik, Universität Mannheim, D–68131 Mannheim
• Email: steidl@kiwi.math.uni-mannheim.de
• Manfred Tasche
• Affiliation: Fachbereich Mathematik, Universität Rostock, D–18051 Rostock
• Email: manfred.tasche@mathematik.uni-rostock.de
• Received by editor(s): March 15, 1996
• Received by editor(s) in revised form: March 13, 1997

• Dedicated: Dedicated to Professor G. Maess on the occasion of his 60th birthday