{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:56:29Z","timestamp":1776848189012,"version":"3.51.2"},"reference-count":46,"publisher":"American Mathematical Society (AMS)","issue":"312","license":[{"start":{"date-parts":[[2018,11,6]],"date-time":"2018-11-06T00:00:00Z","timestamp":1541462400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1522577"],"award-info":[{"award-number":["1522577"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000608","name":"London Mathematical Society","doi-asserted-by":"publisher","award":["1522577"],"award-info":[{"award-number":["1522577"]}],"id":[{"id":"10.13039\/501100000608","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["1522577"],"award-info":[{"award-number":["1522577"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Many standard conversion matrices between coefficients in classical orthogonal polynomial expansions can be decomposed using diagonally-scaled Hadamard products involving Toeplitz and Hankel matrices. This allows us to derive algorithms with an observed complexity of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper O left-parenthesis upper N log squared upper N right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mspace width=\"negativethinmathspace\"\/>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {O}(N\\log ^2 \\! N)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , based on the fast Fourier transform, for converting coefficients of a degree\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N\">\n                        <mml:semantics>\n                          <mml:mi>N<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">N<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    polynomial in one polynomial basis to coefficients in another. Numerical results show that this approach is competitive with state-of-the-art techniques, requires no precomputational cost, can be implemented in a handful of lines of code, and is easily adapted to extended precision arithmetic.\n                  <\/p>","DOI":"10.1090\/mcom\/3277","type":"journal-article","created":{"date-parts":[[2017,4,5]],"date-time":"2017-04-05T11:41:44Z","timestamp":1491392504000},"page":"1913-1934","source":"Crossref","is-referenced-by-count":43,"title":["Fast polynomial transforms based on Toeplitz and Hankel matrices"],"prefix":"10.1090","volume":"87","author":[{"given":"Alex","family":"Townsend","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Webb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheehan","family":"Olver","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2017,11,6]]},"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"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1137\/0917059","article-title":"Rapid computation of the discrete Fourier transform","volume":"17","author":"Anderson, Chris","year":"1996","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970470","volume-title":"Orthogonal polynomials and special functions","author":"Askey, Richard","year":"1975"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/PL00005392","article-title":"The condition number of real Vandermonde, Krylov and positive definite Hankel matrices","volume":"85","author":"Beckermann, Bernhard","year":"2000","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0377-0427(98)00116-2","article-title":"How to choose modified moments?","volume":"98","author":"Beckermann, Bernhard","year":"1998","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1137\/16M1096426","article-title":"On the singular values of matrices with displacement structure","volume":"38","author":"Beckermann, Bernhard","year":"2017","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","article-title":"Julia: a fresh approach to numerical computing","volume":"59","author":"Bezanson, Jeff","year":"2017","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/110829568","article-title":"On rapid computation of expansions in ultraspherical polynomials","volume":"50","author":"Cantero, Mar\u00eda Jos\u00e9","year":"2012","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"9","unstructured":"G. S. Chirikjian and A. B. Kyatkin, Harmonic Analysis for Engineers and Applied Scientists, CRC Press, Second edition, 2000"},{"issue":"6","key":"10","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1137\/0731079","article-title":"The Chebyshev-Legendre method: implementing Legendre methods on Chebyshev points","volume":"31","author":"Don, Wai Sun","year":"1994","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"11","unstructured":"T. A. Driscoll, N. Hale, and L. N. Trefethen, Chebfun Guide, Pafnuty Publications, Oxford, 2014."},{"key":"12","doi-asserted-by":"crossref","unstructured":"M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE, 93 (2005), pp. 216\u2013231.","DOI":"10.1109\/JPROC.2004.840301"},{"key":"13","series-title":"Johns Hopkins Studies in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","author":"Golub, Gene H.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781421407944","edition":"4"},{"key":"14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1145\/355602.361311","article-title":"Implementing Clenshaw-Curtis quadrature. II. Computing the cosine transformation","volume":"15","author":"Gentleman, W. Morvin","year":"1972","journal-title":"Comm. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"print"},{"key":"15","first-page":"76","article-title":"Strong rank revealing Cholesky factorization","volume":"17","author":"Gu, M.","year":"2004","journal-title":"Electron. Trans. Numer. Anal."},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"A148--A167","DOI":"10.1137\/130932223","article-title":"A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula","volume":"36","author":"Hale, Nicholas","year":"2014","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"A1207--A1220","DOI":"10.1137\/140955835","article-title":"An algorithm for the convolution of Legendre series","volume":"36","author":"Hale, Nicholas","year":"2014","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"4","key":"18","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1093\/imanum\/drv060","article-title":"A fast FFT-based discrete Legendre transform","volume":"36","author":"Hale, Nicholas","year":"2016","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"4","key":"19","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.apnum.2011.10.001","article-title":"On the low-rank approximation by the pivoted Cholesky decomposition","volume":"62","author":"Harbrecht, Helmut","year":"2012","journal-title":"Appl. Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0168-9274","issn-type":"print"},{"key":"20","isbn-type":"print","first-page":"161","article-title":"Analysis of the Cholesky decomposition of a semi-definite matrix","author":"Higham, Nicholas J.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0198535643"},{"key":"21","first-page":"23","article-title":"Fast evaluation of real and complex exponential sums","volume":"46","author":"Kunis, Stefan","year":"2017","journal-title":"Electron. Trans. Numer. Anal."},{"issue":"3","key":"22","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00211-010-0352-1","article-title":"A fast and simple algorithm for the computation of Legendre coefficients","volume":"117","author":"Iserles, Arieh","year":"2011","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"2151","DOI":"10.1137\/070703065","article-title":"Computing with expansions in Gegenbauer polynomials","volume":"31","author":"Keiner, Jens","year":"2009","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"24","unstructured":"J. Keiner, Fast Polynomial Transforms, Logos Verlag Berlin GmbH, 2011."},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s11075-008-9184-9","article-title":"Connection coefficients between orthogonal polynomials and the canonical sequence: an approach based on symbolic computation","volume":"47","author":"Maroni, P.","year":"2008","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"key":"26","isbn-type":"print","volume-title":"Chebyshev polynomials","author":"Mason, J. C.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0849303559"},{"key":"27","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1080\/03081087408817070","article-title":"Equalities and inequalities for ranks of matrices","volume":"2","author":"Marsaglia, George","year":"1974","journal-title":"Linear and Multilinear Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0308-1087","issn-type":"print"},{"issue":"9","key":"28","first-page":"3612","article-title":"An improvement on Orszag\u2019s fast algorithm for Legendre polynomial transform","volume":"40","author":"Mori, Akiko","year":"1999","journal-title":"Trans. Inform. Process. Soc. Japan","ISSN":"https:\/\/id.crossref.org\/issn\/0387-5806","issn-type":"print"},{"key":"29","series-title":"Numerical Mathematics and Scientific Computation","isbn-type":"print","volume-title":"Iterative methods for Toeplitz systems","author":"Ng, Michael K.","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0198504209"},{"key":"30","unstructured":"S. Olver, R. M. Slevinsky, et al., https:\/\/github.com\/ApproxFun\/ApproxFun.jl, v0.1.0, 2016."},{"key":"31","isbn-type":"print","volume-title":"NIST handbook of mathematical functions","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521140638"},{"issue":"3","key":"32","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1137\/120865458","article-title":"A fast and well-conditioned spectral method","volume":"55","author":"Olver, Sheehan","year":"2013","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"key":"33","unstructured":"S. A. Orszag, Fast eigenfunction transforms, Science and Computers, Academic Press, New York, (1986), pp. 23\u201330."},{"key":"34","series-title":"Springer Monographs in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21681-2","volume-title":"Hankel operators and their applications","author":"Peller, Vladimir V.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0387955488"},{"issue":"224","key":"35","doi-asserted-by":"publisher","first-page":"1577","DOI":"10.1090\/S0025-5718-98-00975-2","article-title":"Fast algorithms for discrete polynomial transforms","volume":"67","author":"Potts, Daniel","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1-2","key":"36","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/S0377-0427(00)00679-8","article-title":"Some connection and linearization problems for polynomials in and beyond the Askey scheme","volume":"133","author":"S\u00e1nchez-Ruiz, Jorge","year":"2001","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"6","key":"37","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1137\/0915089","article-title":"Efficient spectral-Galerkin method. I. Direct solvers of second- and fourth-order equations using Legendre polynomials","volume":"15","author":"Shen, Jie","year":"1994","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"38","unstructured":"J. Shen, Y. Wang, and J. Xia, Fast structured Jacobi-Jacobi transforms, preprint, 2016."},{"key":"39","doi-asserted-by":"crossref","unstructured":"R. M. Slevinsky, On the use of Hahn\u2019s asymptotic formula and stabilized recurrence for a fast, simple, and stable Chebyshev\u2013Jacobi transform, to appear in IMA Numer. Anal., 2017.","DOI":"10.1093\/imanum\/drw070"},{"key":"40","series-title":"American Mathematical Society Colloquium Publications, Vol. 23","volume-title":"Orthogonal polynomials","author":"Szeg\u00f6, Gabor","year":"1959"},{"key":"41","unstructured":"R. M. Slevinsky, S. Olver, et al. https:\/\/github.com\/MikaelSlevinsky\/FastTransforms.jl, v0.0.6, 2016."},{"issue":"2173","key":"42","doi-asserted-by":"publisher","first-page":"20140585","DOI":"10.1098\/rspa.2014.0585","article-title":"Continuous analogues of matrix factorizations","volume":"471","author":"Townsend, Alex","year":"2015","journal-title":"Proc. A","ISSN":"https:\/\/id.crossref.org\/issn\/1364-5021","issn-type":"print"},{"key":"43","isbn-type":"print","volume-title":"Approximation theory and approximation practice","author":"Trefethen, Lloyd N.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972399"},{"key":"44","unstructured":"H. Wang and D. Huybrechs, Fast and highly accurate computation of Chebyshev expansion coefficients of analytic functions, arXiv preprint. arXiv: 1404.2463 (2014)."},{"key":"45","unstructured":"M. Webb and S. Olver, Spectra of Jacobi operators via connection coefficient matrices, arXiv preprint. arXiv: 1702.03095 (2017)."},{"issue":"2-3","key":"46","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1016\/j.laa.2007.05.027","article-title":"A fast symmetric SVD algorithm for square Hankel matrices","volume":"428","author":"Xu, Wei","year":"2008","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03277-4\/mcom3277_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03277-4\/S0025-5718-2017-03277-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03277-4\/S0025-5718-2017-03277-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:41:23Z","timestamp":1776800483000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-312\/S0025-5718-2017-03277-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,6]]},"references-count":46,"journal-issue":{"issue":"312","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S0025-5718-2017-03277-4"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3277","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":[[2017,11,6]]}}}