{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:36:28Z","timestamp":1776846988814,"version":"3.51.2"},"reference-count":20,"publisher":"American Mathematical Society (AMS)","issue":"224","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Consider the Vandermonde-like matrix\n \n \n \n \n \n \n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n :=<\/mml:mo>\n (<\/mml:mo>\n \n P<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n cos<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \n j<\/mml:mi>\n \n \u03c0\n \n <\/mml:mi>\n <\/mml:mrow>\n N<\/mml:mi>\n <\/mml:mfrac>\n )<\/mml:mo>\n \n )<\/mml:mo>\n \n j<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n N<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n {\\mathbf {P}}:=(P_k(\\cos \\frac {j\\pi }{N}))_{j,k=0}^N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where the polynomials\n \n \n \n \n P<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n P_k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n satisfy a three-term recurrence relation. If\n \n \n \n \n P<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n P_k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are the Chebyshev polynomials\n \n \n \n \n T<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n T_k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , then\n \n \n \n \n \n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n {\\mathbf {P}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n coincides with\n \n \n \n \n \n \n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n \n N<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n :=<\/mml:mo>\n (<\/mml:mo>\n cos<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n \n \n j<\/mml:mi>\n k<\/mml:mi>\n \n \u03c0\n \n <\/mml:mi>\n <\/mml:mrow>\n N<\/mml:mi>\n <\/mml:mfrac>\n \n )<\/mml:mo>\n \n j<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n N<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n {\\mathbf {C}}_{N+1}:= (\\cos \\frac {jk\\pi }{N})_{j,k=0}^N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This paper presents a new fast algorithm for the computation of the matrix-vector product\n \n \n \n \n \n P<\/mml:mi>\n a<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n {\\mathbf {Pa}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n N<\/mml:mi>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(N \\log ^2N)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n arithmetical operations. The algorithm divides into a fast transform which replaces\n \n \n \n \n \n P<\/mml:mi>\n a<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n {\\mathbf {Pa}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with\n \n \n \n \n \n \n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n \n N<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \n \n \n \n a<\/mml:mi>\n \n ~\n \n <\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mrow>\n {\\mathbf {C}}_{N+1} {\\mathbf {\\tilde a}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n 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\n \n \n \n \n \n P<\/mml:mi>\n a<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n {\\mathbf {Pa}}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with almost the same precision as the Clenshaw algorithm, but is much faster for\n \n \n \n \n N<\/mml:mi>\n \n \u2265\n \n <\/mml:mo>\n 128<\/mml:mn>\n <\/mml:mrow>\n N\\ge 128<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-98-00975-2","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1577-1590","source":"Crossref","is-referenced-by-count":73,"title":["Fast algorithms for discrete polynomial transforms"],"prefix":"10.1090","volume":"67","author":[{"given":"Daniel","family":"Potts","sequence":"first","affiliation":[]},{"given":"Gabriele","family":"Steidl","sequence":"additional","affiliation":[]},{"given":"Manfred","family":"Tasche","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/0912009","article-title":"A fast algorithm for the evaluation of Legendre expansions","volume":"12","author":"Alpert, Bradley K.","year":"1991","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"key":"2","doi-asserted-by":"crossref","unstructured":"G. Baszenski and M. Tasche, Fast polynomial multiplication and convolutions related to the discrete cosine transform, Linear Algebra Appl. 252 (1997), 1 \u2013 25.","DOI":"10.1016\/0024-3795(95)00696-6"},{"issue":"3","key":"3","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0377-0427(90)90041-W","article-title":"On the associated orthogonal polynomials","volume":"32","author":"Belmehdi, S.","year":"1990","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"4","series-title":"Mathematics and its Applications, Vol. 13","isbn-type":"print","volume-title":"An introduction to orthogonal polynomials","author":"Chihara, T. S.","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0677041500"},{"key":"5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.2307\/1989990","article-title":"Steinitz field towers for modular fields","volume":"46","author":"MacLane, Saunders","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/aama.1994.1008","article-title":"Computing Fourier transforms and convolutions on the 2-sphere","volume":"15","author":"Driscoll, James R.","year":"1994","journal-title":"Adv. in Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-8858","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"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\u20131099.","DOI":"10.1137\/S0097539792240121"},{"issue":"5","key":"8","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1137\/0733082","article-title":"Fast algorithms for polynomial interpolation, integration, and differentiation","volume":"33","author":"Dutt, A.","year":"1996","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0024-3795(83)80020-2","article-title":"The condition of Vandermonde-like matrices involving orthogonal polynomials","volume":"52\/53","author":"Gautschi, Walter","year":"1983","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"10","unstructured":"D. M. Healy, S. Moore and D. Rockmore, Efficiency and stability issues in the numerical convolution of Fourier transforms and convolutions on the 2\u2013sphere, Technical Report, Dartmouth College, 1994."},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1093\/imanum\/8.4.473","article-title":"Fast solution of Vandermonde-like systems involving orthogonal polynomials","volume":"8","author":"Higham, Nicholas J.","year":"1988","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"key":"12","unstructured":"D. Maslen, A polynomial approach to orthogonal polynomial transforms, Research Report, Max\u2013Planck\u2013Institute of Mathematics, Bonn, 1994."},{"key":"13","unstructured":"S. S. B. Moore, Efficient stabilization methods for fast polynomial transforms, Thesis, Dartmouth College, 1994."},{"key":"14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0024-3795(93)90246-K","article-title":"Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation","volume":"192","author":"Moore, Sean S. B.","year":"1993","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"15","unstructured":"S. A. Orszag, Fast eigenfunction transforms, in: Science and Computers (G.C. Rota, ed.), Academic Press, New York, 1986, 23 \u2013 30."},{"key":"16","doi-asserted-by":"crossref","unstructured":"V. Pan, Fast evaluation and interpolation at the Chebyshev sets of points, Appl. Math. Lett. 34 (1989), 255 \u2013 258.","DOI":"10.1016\/0893-9659(89)90064-5"},{"key":"17","isbn-type":"print","volume-title":"Discrete cosine transform","author":"Rao, K. R.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/012580203X"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01189022","article-title":"Fast radix-\ud835\udc5d discrete cosine transform","volume":"3","author":"Steidl, Gabriele","year":"1992","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"193","key":"19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2008542","article-title":"A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms","volume":"56","author":"Steidl, G.","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"20","series-title":"Applicable Mathematics Series","isbn-type":"print","volume-title":"Computation with recurrence relations","author":"Wimp, Jet","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0273085085"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00975-2\/S0025-5718-98-00975-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00975-2\/S0025-5718-98-00975-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:51:45Z","timestamp":1776721905000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00975-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":20,"journal-issue":{"issue":"224","published-print":{"date-parts":[[1998,10]]}},"alternative-id":["S0025-5718-98-00975-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00975-2","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}