Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Fast algorithms for discrete polynomial transforms


Authors: Daniel Potts, Gabriele Steidl and Manfred Tasche
Journal: Math. Comp. 67 (1998), 1577-1590
MSC (1991): Primary 65T99, 42C10, 33C25
MathSciNet review: 1474655
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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^2\!N)$ 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$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society 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: 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

DOI: http://dx.doi.org/10.1090/S0025-5718-98-00975-2
PII: S 0025-5718(98)00975-2
Keywords: Discrete polynomial transform, Vandermonde-like matrix, fast cosine transform, fast polynomial transform, Chebyshev knots, cascade summation
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
Article copyright: © Copyright 1998 American Mathematical Society