Remote Access Mathematics of Computation
Green Open Access

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

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?)

  • 1. B. K. Alpert and V. Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM J. Sci. Statist. Comput. 12 (1991), 158 - 179. MR 91i:65042
  • 2. G. Baszenski and M. Tasche, Fast polynomial multiplication and convolutions related to the discrete cosine transform, Linear Algebra Appl. 252 (1997), 1 - 25. CMP 97:06
  • 3. S. Belmehdi, On the associated orthogonal polynomials, J. Comput. Appl. Math. 32 (1991), 311 - 319. MR 92e:33007
  • 4. T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, New York, 1978. MR 58:1979
  • 5. C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Comp. 9 (1955), 118 - 120. MR 17:194e
  • 6. J. R. Driscoll and D.M. Healy, Computing Fourier transforms and convolutions on the 2-sphere, Adv. in Appl. Math. 15 (1994), 202 - 240. MR 95h:65108
  • 7. J. R. Driscoll, D. M. Healy and D. Rockmore, Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs, SIAM J. Sci. Comput. 26 (1997), 1066-1099. CMP 97:15
  • 8. A. Dutt, M. Gu and V. Rokhlin, Fast algorithms for polynomial interpolation, integration and differentiation, SIAM J. Numer. Anal. 33 (1996), 1689-1711. MR 97h:65015
  • 9. W. Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl. ${\mathbf{{52}}}/{\mathbf{{53}}}$ (1983), 293 - 300. MR 84i:65043
  • 10. D. M. Healy, S. Moore and D. Rockmore, Efficiency and stability issues in the numerical convolution of Fourier transforms and convolutions on the 2-sphere, Technical Report, Dartmouth College, 1994.
  • 11. N. J. Higham, Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMA J. Numer. Anal. ${\mathbf{{8}}}$ (1988), 473 - 486. MR 89k:65067
  • 12. D. Maslen, A polynomial approach to orthogonal polynomial transforms, Research Report, Max-Planck-Institute of Mathematics, Bonn, 1994.
  • 13. S. S. B. Moore, Efficient stabilization methods for fast polynomial transforms, Thesis, Dartmouth College, 1994.
  • 14. S. S. B. Moore, D.M. Healy and D.N. Rockmore, Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation, Linear Algebra Appl. 192 (1993), 249 - 299. MR 94g:65148
  • 15. S. A. Orszag, Fast eigenfunction transforms, in: Science and Computers (G.C. Rota, ed.), Academic Press, New York, 1986, 23 - 30.
  • 16. V. Pan, Fast evaluation and interpolation at the Chebyshev sets of points, Appl. Math. Lett. 34 (1989), 255 - 258. CMP 21:17
  • 17. K. R. Rao and P. Yip, Discrete Cosine Transform, Academic Press, Boston, 1990. MR 92b:94003
  • 18. G. Steidl, Fast radix-$p$ discrete cosine transform, Appl. Algebra in Engrg. Comm. Comput. 3 (1992), 39 - 46. MR 95m:65221
  • 19. G. Steidl and M. Tasche, A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms, Math. Comp. 56 (1991), 281 - 296. MR 91h:65225
  • 20. J. Wimp, Computation with Recurrence Relations, Pitman Press, Boston, 1984. MR 85f:65001

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

Gabriele Steidl
Affiliation: Fakultät für Mathematik und Informatik, Universität Mannheim, D–68131 Mannheim

Manfred Tasche
Affiliation: Fachbereich Mathematik, Universität Rostock, D–18051 Rostock

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

American Mathematical Society