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

DOI:
https://doi.org/10.1090/S0025-5718-98-00975-2

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 ^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$.

- Bradley K. Alpert and Vladimir Rokhlin,
*A fast algorithm for the evaluation of Legendre expansions*, SIAM J. Sci. Statist. Comput.**12**(1991), no. 1, 158–179. MR**1078802**, DOI https://doi.org/10.1137/0912009 - G. Baszenski and M. Tasche, Fast polynomial multiplication and convolutions related to the discrete cosine transform, Linear Algebra Appl.
**252**(1997), 1 – 25. - S. Belmehdi,
*On the associated orthogonal polynomials*, J. Comput. Appl. Math.**32**(1990), no. 3, 311–319. MR**1090883**, DOI https://doi.org/10.1016/0377-0427%2890%2990041-W - T. S. Chihara,
*An introduction to orthogonal polynomials*, Gordon and Breach Science Publishers, New York-London-Paris, 1978. Mathematics and its Applications, Vol. 13. MR**0481884** - C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Comp.
**9**(1955), 118 – 120. - James R. Driscoll and Dennis M. Healy Jr.,
*Computing Fourier transforms and convolutions on the $2$-sphere*, Adv. in Appl. Math.**15**(1994), no. 2, 202–250. MR**1277214**, DOI https://doi.org/10.1006/aama.1994.1008 - 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. - A. Dutt, M. Gu, and V. Rokhlin,
*Fast algorithms for polynomial interpolation, integration, and differentiation*, SIAM J. Numer. Anal.**33**(1996), no. 5, 1689–1711. MR**1411845**, DOI https://doi.org/10.1137/0733082 - Walter Gautschi,
*The condition of Vandermonde-like matrices involving orthogonal polynomials*, Linear Algebra Appl.**52/53**(1983), 293–300. MR**709357**, DOI https://doi.org/10.1016/0024-3795%2883%2980020-2 - 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.
- Nicholas J. Higham,
*Fast solution of Vandermonde-like systems involving orthogonal polynomials*, IMA J. Numer. Anal.**8**(1988), no. 4, 473–486. MR**975608**, DOI https://doi.org/10.1093/imanum/8.4.473 - D. Maslen, A polynomial approach to orthogonal polynomial transforms, Research Report, Max–Planck–Institute of Mathematics, Bonn, 1994.
- S. S. B. Moore, Efficient stabilization methods for fast polynomial transforms, Thesis, Dartmouth College, 1994.
- Sean S. B. Moore, Dennis M. Healy Jr., and Daniel N. Rockmore,
*Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation*, Linear Algebra Appl.**192**(1993), 249–299. Computational linear algebra in algebraic and related problems (Essen, 1992). MR**1236746**, DOI https://doi.org/10.1016/0024-3795%2893%2990246-K - S. A. Orszag, Fast eigenfunction transforms, in:
*Science and Computers*(G.C. Rota, ed.), Academic Press, New York, 1986, 23 – 30. - V. Pan, Fast evaluation and interpolation at the Chebyshev sets of points, Appl. Math. Lett.
**34**(1989), 255 – 258. - K. R. Rao and P. Yip,
*Discrete cosine transform*, Academic Press, Inc., Boston, MA, 1990. Algorithms, advantages, applications. MR**1080969** - Gabriele Steidl,
*Fast radix-$p$ discrete cosine transform*, Appl. Algebra Engrg. Comm. Comput.**3**(1992), no. 1, 39–46. MR**1325744**, DOI https://doi.org/10.1007/BF01189022 - G. Steidl and M. Tasche,
*A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms*, Math. Comp.**56**(1991), no. 193, 281–296. MR**1052103**, DOI https://doi.org/10.1090/S0025-5718-1991-1052103-1 - Jet Wimp,
*Computation with recurrence relations*, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR**727118**

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:
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

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