Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Fast polynomial transforms based on Toeplitz and Hankel matrices


Authors: Alex Townsend, Marcus Webb and Sheehan Olver
Journal: Math. Comp.
MSC (2010): Primary 65T50, 65D05, 15B05
DOI: https://doi.org/10.1090/mcom/3277
Published electronically: November 6, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \smash {\mathcal {O}(N\log ^2 \! N)}$, based on the fast Fourier transform, for converting coefficients of a degree $ 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.


References [Enhancements On Off] (What's this?)

  • [1] 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
  • [2] Chris Anderson and Marie Dillon Dahleh, Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput. 17 (1996), no. 4, 913-919. MR 1395355
  • [3] Richard Askey, Orthogonal polynomials and special functions, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1975. MR 0481145
  • [4] Bernhard Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math. 85 (2000), no. 4, 553-577. MR 1771780
  • [5] Bernhard Beckermann and Emmanuel Bourreau, How to choose modified moments?, J. Comput. Appl. Math. 98 (1998), no. 1, 81-98. MR 1656990
  • [6] Bernhard Beckermann and Alex Townsend, On the Singular Values of Matrices with Displacement Structure, SIAM J. Matrix Anal. Appl. 38 (2017), no. 4, 1227-1248. MR 3717820
  • [7] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B. Shah, Julia: a fresh approach to numerical computing, SIAM Rev. 59 (2017), no. 1, 65-98. MR 3605826
  • [8] María José Cantero and Arieh Iserles, On rapid computation of expansions in ultraspherical polynomials, SIAM J. Numer. Anal. 50 (2012), no. 1, 307-327. MR 2888315
  • [9] G. S. CHIRIKJIAN AND A. B. KYATKIN, Harmonic Analysis for Engineers and Applied Scientists, CRC Press, Second edition, 2000
  • [10] Wai Sun Don and David Gottlieb, The Chebyshev-Legendre method: implementing Legendre methods on Chebyshev points, SIAM J. Numer. Anal. 31 (1994), no. 6, 1519-1534. MR 1302673
  • [11] T. A. DRISCOLL, N. HALE, AND L. N. TREFETHEN, Chebfun Guide, Pafnuty Publications, Oxford, 2014.
  • [12] M. FRIGO AND S. G. JOHNSON, The design and implementation of FFTW3, Proc. IEEE, 93 (2005), pp. 216-231.
  • [13] Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
  • [14] W. Morvin Gentleman, Implementing Clenshaw-Curtis quadrature. II. Computing the cosine transformation, Comm. ACM 15 (1972), 343-346. MR 0327002
  • [15] M. Gu and L. Miranian, Strong rank revealing Cholesky factorization, Electron. Trans. Numer. Anal. 17 (2004), 76-92. MR 2040798
  • [16] Nicholas Hale and Alex Townsend, A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula, SIAM J. Sci. Comput. 36 (2014), no. 1, A148-A167. MR 3163249
  • [17] Nicholas Hale and Alex Townsend, An algorithm for the convolution of Legendre series, SIAM J. Sci. Comput. 36 (2014), no. 3, A1207-A1220. MR 3217220
  • [18] Nicholas Hale and Alex Townsend, A fast FFT-based discrete Legendre transform, IMA J. Numer. Anal. 36 (2016), no. 4, 1670-1684. MR 3556400
  • [19] Helmut Harbrecht, Michael Peters, and Reinhold Schneider, On the low-rank approximation by the pivoted Cholesky decomposition, Appl. Numer. Math. 62 (2012), no. 4, 428-440. MR 2899254
  • [20] Nicholas J. Higham, Analysis of the Cholesky decomposition of a semi-definite matrix, Reliable numerical computation, Oxford Sci. Publ., Oxford Univ. Press, New York, 1990, pp. 161-185. MR 1098323
  • [21] Stefan Kunis and Ines Melzer, Fast evaluation of real and complex exponential sums, Electron. Trans. Numer. Anal. 46 (2017), 23-35. MR 3614469
  • [22] Arieh Iserles, A fast and simple algorithm for the computation of Legendre coefficients, Numer. Math. 117 (2011), no. 3, 529-553. MR 2772418
  • [23] Jens Keiner, Computing with expansions in Gegenbauer polynomials, SIAM J. Sci. Comput. 31 (2009), no. 3, 2151-2171. MR 2516147
  • [24] J. KEINER, Fast Polynomial Transforms, Logos Verlag Berlin GmbH, 2011.
  • [25] P. Maroni and Z. da Rocha, Connection coefficients between orthogonal polynomials and the canonical sequence: an approach based on symbolic computation, Numer. Algorithms 47 (2008), no. 3, 291-314. MR 2385739
  • [26] J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
  • [27] George Marsaglia and George P. H. Styan, Equalities and inequalities for ranks of matrices, Linear and Multilinear Algebra 2 (1974/75), 269-292. MR 0384840
  • [28] Akiko Mori, Reiji Suda, and Masaaki Sugihara, An improvement on Orszag's fast algorithm for Legendre polynomial transform, Trans. Inform. Process. Soc. Japan 40 (1999), no. 9, 3612-3615 (Japanese, with English and Japanese summaries). MR 1724286
  • [29] Michael K. Ng, Iterative methods for Toeplitz systems, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. MR 2108963
  • [30] S. OLVER, R. M. SLEVINSKY, et al., https://github.com/ApproxFun/ApproxFun.jl, v0.1.0, 2016.
  • [31] Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark (eds.), NIST handbook of mathematical functions, U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC; Cambridge University Press, Cambridge, 2010. With 1 CD-ROM (Windows, Macintosh and UNIX). MR 2723248
  • [32] Sheehan Olver and Alex Townsend, A fast and well-conditioned spectral method, SIAM Rev. 55 (2013), no. 3, 462-489. MR 3089410
  • [33] S. A. ORSZAG, Fast eigenfunction transforms, Science and Computers, Academic Press, New York, (1986), pp. 23-30.
  • [34] Vladimir V. Peller, Hankel operators and their applications, Springer Monographs in Mathematics, Springer-Verlag, New York, 2003. MR 1949210
  • [35] Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast algorithms for discrete polynomial transforms, Math. Comp. 67 (1998), no. 224, 1577-1590. MR 1474655
  • [36] Jorge Sánchez-Ruiz and Jesús S. Dehesa, Some connection and linearization problems for polynomials in and beyond the Askey scheme, Proceedings of the Fifth International Symposium on Orthogonal Polynomials, Special Functions and their Applications (Patras, 1999), 2001, pp. 579-591. MR 1858314
  • [37] Jie Shen, Efficient spectral-Galerkin method. I. Direct solvers of second- and fourth-order equations using Legendre polynomials, SIAM J. Sci. Comput. 15 (1994), no. 6, 1489-1505. MR 1298626
  • [38] J. SHEN, Y. WANG, AND J. XIA, Fast structured Jacobi-Jacobi transforms, preprint, 2016.
  • [39] R. M. SLEVINSKY, On the use of Hahn's asymptotic formula and stabilized recurrence for a fast, simple, and stable Chebyshev-Jacobi transform, to appear in IMA Numer. Anal., 2017.
  • [40] Gabor Szegö, Orthogonal polynomials, American Mathematical Society Colloquium Publications, Vol. 23. Revised ed, American Mathematical Society, Providence, R.I., 1959. MR 0106295
  • [41] R. M. SLEVINSKY, S. OLVER, et al. https://github.com/MikaelSlevinsky/FastTransforms.jl, v0.0.6, 2016.
  • [42] Alex Townsend and Lloyd N. Trefethen, Continuous analogues of matrix factorizations, Proc. A. 471 (2015), no. 2173, 20140585, 21. MR 3285359
  • [43] Lloyd N. Trefethen, Approximation theory and approximation practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
  • [44] H. WANG AND D. HUYBRECHS, Fast and highly accurate computation of Chebyshev expansion coefficients of analytic functions, arXiv preprint. arXiv: 1404.2463 (2014).
  • [45] M. WEBB AND S. OLVER, Spectra of Jacobi operators via connection coefficient matrices, arXiv preprint. arXiv: 1702.03095 (2017).
  • [46] Wei Xu and Sanzheng Qiao, A fast symmetric SVD algorithm for square Hankel matrices, Linear Algebra Appl. 428 (2008), no. 2-3, 550-563. MR 2374566

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65T50, 65D05, 15B05

Retrieve articles in all journals with MSC (2010): 65T50, 65D05, 15B05


Additional Information

Alex Townsend
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: townsend@cornell.edu

Marcus Webb
Affiliation: Department of Computer Science, KU Leuven, 3001 Leuven, Belgium
Email: marcus.webb@cs.kuleuven.be

Sheehan Olver
Affiliation: Department of Mathematics, Imperial College, London SW7 2AZ, United Kingdom
Email: s.olver@imperial.ac.uk

DOI: https://doi.org/10.1090/mcom/3277
Keywords: Conversion matrix, Toeplitz, Hankel, Hadamard product
Received by editor(s): May 10, 2016
Received by editor(s) in revised form: November 20, 2016, and March 9, 2017
Published electronically: November 6, 2017
Additional Notes: The work of the first author was supported by the National Science Foundation grant No. 1522577
The work of the second author was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/H023348/1 for the University of Cambridge Centre for Doctoral Training, the Cambridge Centre for Analysis, and the London Mathematical Society Cecil King Travel Scholarship 2015
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society