Skip to Main Content

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 transforms
HTML articles powered by AMS MathViewer

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


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
Additional Information
  • Daniel Potts
  • Affiliation: Fachbereich Mathematik, Universität Rostock, D–18051 Rostock
  • Email:
  • Gabriele Steidl
  • Affiliation: Fakultät für Mathematik und Informatik, Universität Mannheim, D–68131 Mannheim
  • Email:
  • Manfred Tasche
  • Affiliation: Fachbereich Mathematik, Universität Rostock, D–18051 Rostock
  • Email:
  • 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
  • © Copyright 1998 American Mathematical Society
  • Journal: Math. Comp. 67 (1998), 1577-1590
  • MSC (1991): Primary 65T99, 42C10, 33C25
  • DOI:
  • MathSciNet review: 1474655