Fast polynomial transforms based on Toeplitz and Hankel matrices

Townsend, Alex; Webb, Marcus; Olver, Sheehan

doi:10.1090/mcom/3277

Fast polynomial transforms based on Toeplitz and Hankel matrices
HTML articles powered by AMS MathViewer

by Alex Townsend, Marcus Webb and Sheehan Olver PDF

Math. Comp. 87 (2018), 1913-1934 Request permission

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 $\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

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 10.1137/0912009
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, DOI 10.1137/0917059
Richard Askey, Orthogonal polynomials and special functions, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1975. MR 0481145, DOI 10.1137/1.9781611970470
Bernhard Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math. 85 (2000), no. 4, 553–577. MR 1771780, DOI 10.1007/PL00005392
Bernhard Beckermann and Emmanuel Bourreau, How to choose modified moments?, J. Comput. Appl. Math. 98 (1998), no. 1, 81–98. MR 1656990, DOI 10.1016/S0377-0427(98)00116-2
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, DOI 10.1137/16M1096426
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, DOI 10.1137/141000671
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, DOI 10.1137/110829568
G. S. Chirikjian and A. B. Kyatkin, Harmonic Analysis for Engineers and Applied Scientists, CRC Press, Second edition, 2000
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, DOI 10.1137/0731079
T. A. Driscoll, N. Hale, and L. N. Trefethen, Chebfun Guide, Pafnuty Publications, Oxford, 2014.
M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE, 93 (2005), pp. 216–231.
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
W. Morvin Gentleman, Implementing Clenshaw-Curtis quadrature. II. Computing the cosine transformation, Comm. ACM 15 (1972), 343–346. MR 0327002, DOI 10.1145/355602.361311
M. Gu and L. Miranian, Strong rank revealing Cholesky factorization, Electron. Trans. Numer. Anal. 17 (2004), 76–92. MR 2040798
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, DOI 10.1137/130932223
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, DOI 10.1137/140955835
Nicholas Hale and Alex Townsend, A fast FFT-based discrete Legendre transform, IMA J. Numer. Anal. 36 (2016), no. 4, 1670–1684. MR 3556400, DOI 10.1093/imanum/drv060
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, DOI 10.1016/j.apnum.2011.10.001
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
Stefan Kunis and Ines Melzer, Fast evaluation of real and complex exponential sums, Electron. Trans. Numer. Anal. 46 (2017), 23–35. MR 3614469
Arieh Iserles, A fast and simple algorithm for the computation of Legendre coefficients, Numer. Math. 117 (2011), no. 3, 529–553. MR 2772418, DOI 10.1007/s00211-010-0352-1
Jens Keiner, Computing with expansions in Gegenbauer polynomials, SIAM J. Sci. Comput. 31 (2009), no. 3, 2151–2171. MR 2516147, DOI 10.1137/070703065
J. Keiner, Fast Polynomial Transforms, Logos Verlag Berlin GmbH, 2011.
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, DOI 10.1007/s11075-008-9184-9
J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
George Marsaglia and George P. H. Styan, Equalities and inequalities for ranks of matrices, Linear and Multilinear Algebra 2 (1974/75), 269–292. MR 384840, DOI 10.1080/03081087408817070
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
Michael K. Ng, Iterative methods for Toeplitz systems, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. MR 2108963
S. Olver, R. M. Slevinsky, et al., https://github.com/ApproxFun/ApproxFun.jl, v0.1.0, 2016.
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
Sheehan Olver and Alex Townsend, A fast and well-conditioned spectral method, SIAM Rev. 55 (2013), no. 3, 462–489. MR 3089410, DOI 10.1137/120865458
S. A. Orszag, Fast eigenfunction transforms, Science and Computers, Academic Press, New York, (1986), pp. 23–30.
Vladimir V. Peller, Hankel operators and their applications, Springer Monographs in Mathematics, Springer-Verlag, New York, 2003. MR 1949210, DOI 10.1007/978-0-387-21681-2
Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast algorithms for discrete polynomial transforms, Math. Comp. 67 (1998), no. 224, 1577–1590. MR 1474655, DOI 10.1090/S0025-5718-98-00975-2
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, DOI 10.1016/S0377-0427(00)00679-8
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, DOI 10.1137/0915089
J. Shen, Y. Wang, and J. Xia, Fast structured Jacobi-Jacobi transforms, preprint, 2016.
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.
Gabor Szegö, Orthogonal polynomials, American Mathematical Society Colloquium Publications, Vol. 23, American Mathematical Society, Providence, R.I., 1959. Revised ed. MR 0106295
R. M. Slevinsky, S. Olver, et al. https://github.com/MikaelSlevinsky/FastTransforms.jl, v0.0.6, 2016.
Alex Townsend and Lloyd N. Trefethen, Continuous analogues of matrix factorizations, Proc. A. 471 (2015), no. 2173, 20140585, 21. MR 3285359, DOI 10.1098/rspa.2014.0585
Lloyd N. Trefethen, Approximation theory and approximation practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
H. Wang and D. Huybrechs, Fast and highly accurate computation of Chebyshev expansion coefficients of analytic functions, arXiv preprint. arXiv: 1404.2463 (2014).
M. Webb and S. Olver, Spectra of Jacobi operators via connection coefficient matrices, arXiv preprint. arXiv: 1702.03095 (2017).
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, DOI 10.1016/j.laa.2007.05.027