Fast algorithms for discrete polynomial transforms on arbitrary grids
详细信息 查看全文
- 作者：Potts ; Daniel
- 关键词：Primary 65T50 ; 41A15 ; 41A30 ; 42A16 ; Discrete polynomial transform ; Vandermonde-like matrix ; Fast cosine transform ; Fast Fourier transform ; Fast polynomial transform ; Chebyshev knots ; Nonequispaced grids ; B-splines ; Gaussian bells
- 刊名：Linear Algebra and its Applications
- 出版年：2003
- 出版时间：June 1, 2003
- 年：2003
- 卷：366
- 期：Complete
- 页码：353-370
- 全文大小：168 K
文摘
Consider the Vandermonde-like matrix P:=(Pk(xM,l))l,k=0M,N, where the polynomials Pk satisfy a three-term recurrence relation and xM,l
[−1,1] are arbitrary nodes. If Pk are the Chebyshev polynomials Tk, then P coincides with A:=(Tk(xM,l))l=0,k=0M,N. This paper presents a fast algorithm for the computation of the matrix–vector product Pa in O(Nlog2N) arithmetical operations. The algorithm divides into a fast transform which replaces Pa with Aã and a fast cosine transform on arbitrary nodes (NDCT). Since the first part of the algorithm was considered in [Math. Comp. 67 (1998) 1577], we focus on approximative algorithms for the NDCT. Our considerations are completed by numerical tests.
[−1,1] are arbitrary nodes. If Pk are the Chebyshev polynomials Tk, then P coincides with A:=(Tk(xM,l))l=0,k=0M,N. This paper presents a fast algorithm for the computation of the matrix–vector product Pa in O(Nlog2N) arithmetical operations. The algorithm divides into a fast transform which replaces Pa with Aã and a fast cosine transform on arbitrary nodes (NDCT). Since the first part of the algorithm was considered in [Math. Comp. 67 (1998) 1577], we focus on approximative algorithms for the NDCT. Our considerations are completed by numerical tests.