Fast structured Jacobi-Jacobi transforms
HTML articles powered by AMS MathViewer
- by Jie Shen, Yingwei Wang and Jianlin Xia HTML | PDF
- Math. Comp. 88 (2019), 1743-1772 Request permission
Abstract:
Jacobi polynomials are frequently used in scientific and engineering applications, and often times, one needs to use the so-called Jacobi-Jacobi transforms which are transforms between two Jacobi expansions with different indices. In this paper, we develop a fast structured algorithm for Jacobi-Jacobi transforms. The algorithm is based on two main ingredients. (i) Derive explicit formulas for connection matrices of two Jacobi expansions with arbitrary indices. In particular, if the indices have integer differences, the connection matrices are relatively sparse or highly structured. The benefit of simultaneous promotion or demotion of the indices is shown. (ii) If the indices have non-integer differences, we explore analytically or numerically a low-rank property hidden in the connection matrices. Combining these two ingredients, we develop a fast structured Jacobi-Jacobi transform with nearly linear complexity, after a one-time precomputation with quadratic complexity, between coefficients of two Jacobi expansions with arbitrary indices. An important byproduct of the fast Jacobi-Jacobi transform is the fast Jacobi transform between the function values at a set of Chebyshev-Gauss-type points and coefficients of the Jacobi expansion with arbitrary indices. Ample numerical results are presented to illustrate the computational efficiency and accuracy of our algorithm.References
- H. Alıcı and J. Shen, Highly accurate pseudospectral approximations of the prolate spheroidal wave equation for any bandwidth parameter and zonal wavenumber, J. Sci. Comput. 71 (2017), no. 2, 804–821. MR 3627542, DOI 10.1007/s10915-016-0321-7
- 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
- George E. Andrews, Richard Askey, and Ranjan Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR 1688958, DOI 10.1017/CBO9781107325937
- Tom Bella and Jenna Reis, The spectral connection matrix for classical orthogonal polynomials of a single parameter, Linear Algebra Appl. 458 (2014), 161–182. MR 3231813, DOI 10.1016/j.laa.2014.06.002
- Jenna Reis, The spectral connection matrix for classical real orthogonal polynomials, ProQuest LLC, Ann Arbor, MI, 2015. Thesis (Ph.D.)–University of Rhode Island. MR 3358129
- John P. Boyd, Algorithm 840: computation of grid points, quadrature weights and derivatives for spectral element methods using prolate spheroidal wave functions—prolate elements, ACM Trans. Math. Software 31 (2005), no. 1, 149–165. MR 2291545, DOI 10.1145/1055531.1055538
- Dietrich Braess and Wolfgang Hackbusch, On the efficient computation of high-dimensional integrals and the approximation by exponential sums, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 39–74. MR 2648371, DOI 10.1007/978-3-642-03413-8_{3}
- C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral methods, Scientific Computation, Springer-Verlag, Berlin, 2006. Fundamentals in single domains. MR 2223552
- S. Chandrasekaran, M. Gu, and T. Pals, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl. 28 (2006), no. 3, 603–622. MR 2262971, DOI 10.1137/S0895479803436652
- S. Chandrasekaran and M. Gu, A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices, Numer. Math. 96 (2004), no. 4, 723–731. MR 2036363, DOI 10.1007/s00211-002-0199-1
- Moshe Dubiner, Spectral methods on triangles and other domains, J. Sci. Comput. 6 (1991), no. 4, 345–390. MR 1154903, DOI 10.1007/BF01060030
- C. L. Frenzen, Error bounds for asymptotic expansions of the ratio of two gamma functions, SIAM J. Math. Anal. 18 (1987), no. 3, 890–896. MR 883576, DOI 10.1137/0518067
- David Gottlieb and Chi-Wang Shu, On the Gibbs phenomenon and its resolution, SIAM Rev. 39 (1997), no. 4, 644–668. MR 1491051, DOI 10.1137/S0036144596301390
- L. Greengard and V. Rokhlin, A fast algorithm for particle simulations [ MR0918448 (88k:82007)], J. Comput. Phys. 135 (1997), no. 2, 279–292. With an introduction by John A. Board, Jr.; Commemoration of the 30th anniversary {of J. Comput. Phys.}. MR 1486277, DOI 10.1006/jcph.1997.5706
- Ben-yu Guo, Jacobi approximations in certain Hilbert spaces and their applications to singular differential equations, J. Math. Anal. Appl. 243 (2000), no. 2, 373–408. MR 1741531, DOI 10.1006/jmaa.1999.6677
- Ben-yu Guo and Li-lian Wang, Jacobi approximations in non-uniformly Jacobi-weighted Sobolev spaces, J. Approx. Theory 128 (2004), no. 1, 1–41. MR 2063010, DOI 10.1016/j.jat.2004.03.008
- 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
- George Em Karniadakis and Spencer J. Sherwin, Spectral/$hp$ element methods for CFD, 2nd ed., Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013. MR 3088105
- Jens Keiner, Gegenbauer polynomials and semiseparable matrices, Electron. Trans. Numer. Anal. 30 (2008), 26–53. MR 2480068
- Jens Keiner, Computing with expansions in Gegenbauer polynomials, SIAM J. Sci. Comput. 31 (2009), no. 3, 2151–2171. MR 2516147, DOI 10.1137/070703065
- Tom Koornwinder, Two-variable analogues of the classical orthogonal polynomials, Theory and application of special functions (Proc. Advanced Sem., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1975) Math. Res. Center, Univ. Wisconsin, Publ. No. 35, Academic Press, New York, 1975, pp. 435–495. MR 0402146
- Stanisław Lewanowicz, Quick construction of recurrence relations for the Jacobi coefficients, J. Comput. Appl. Math. 43 (1992), no. 3, 355–372. MR 1193813, DOI 10.1016/0377-0427(92)90021-O
- Huiyuan Li and Jie Shen, Optimal error estimates in Jacobi-weighted Sobolev spaces for polynomial approximations on the triangle, Math. Comp. 79 (2010), no. 271, 1621–1646. MR 2630005, DOI 10.1090/S0025-5718-09-02308-4
- José Luis López and Nico M. Temme, Large degree asymptotics of generalized Bernoulli and Euler polynomials, J. Math. Anal. Appl. 363 (2010), no. 1, 197–208. MR 2559053, DOI 10.1016/j.jmaa.2009.08.034
- 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
- Pascal Maroni and Zélia da Rocha, Connection coefficients for orthogonal polynomials: symbolic computations, verifications and demonstrations in the Mathematica language, Numer. Algorithms 63 (2013), no. 3, 507–520. MR 3071188, DOI 10.1007/s11075-012-9634-2
- 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
- Akil Narayan and Jan S. Hesthaven, Computation of connection coefficients and measure modifications for orthogonal polynomials, BIT 52 (2012), no. 2, 457–483. MR 2931359, DOI 10.1007/s10543-011-0363-z
- F. W. J. Olver, Airy and related functions, NIST handbook of mathematical functions, U.S. Dept. Commerce, Washington, DC, 2010, pp. 193–213. MR 2655349
- S. A. Orszag, Fast eigenfunction transforms, Science and Computers, Adv. Math. Supplementary Studies (G. C. Rota, ed.), vol. 10, Academic Press, New York, USA, 1986, pp. 23–30.
- Vladimir Rokhlin and Mark Tygert, Fast algorithms for spherical harmonic expansions, SIAM J. Sci. Comput. 27 (2006), no. 6, 1903–1928. MR 2211433, DOI 10.1137/050623073
- A. Ronveaux, A. Zarzo, and E. Godoy, Recurrence relations for connection coefficients between two families of orthogonal polynomials, J. Comput. Appl. Math. 62 (1995), no. 1, 67–73. MR 1361274, DOI 10.1016/0377-0427(94)00079-8
- Herbert E. Salzer, A recurrence scheme for converting from one orthogonal expansion into another, Comm. ACM 16 (1973), no. 11, 705–707. MR 0395158, DOI 10.1145/355611.362548
- J. Shen, Effcient Chebyshev-Legendre Galerkin methods for elliptic problems, Proceedings of ICOSAHOM’95 34 (1996), 233–239.
- J. Shen, T. Tang, and L.-L. Wang, Spectral Methods: Algorithms, Analysis and Applications, Springer Series in Computational Mathematics, no. 41, Springer-Verlag, Berlin-Heidelberg, 2011.
- Jie Shen and Yingwei Wang, Müntz-Galerkin methods and applications to mixed Dirichlet-Neumann boundary value problems, SIAM J. Sci. Comput. 38 (2016), no. 4, A2357–A2381. MR 3531734, DOI 10.1137/15M1052391
- R. M. Slevinsky, On the use of Hahn’s asymptotic formula and stabilized recurrence for a fast, simple and stable Chebyshev–Jacobi transform, IMA Journal of Numerical Analysis (2017), drw070.
- Reiji Suda and Masayasu Takami, A fast spherical harmonics transform algorithm, Math. Comp. 71 (2002), no. 238, 703–715. MR 1885622, DOI 10.1090/S0025-5718-01-01386-2
- Paul N. Swarztrauber and William F. Spotz, Generalized discrete spherical harmonic transforms, J. Comput. Phys. 159 (2000), no. 2, 213–230. MR 1752616, DOI 10.1006/jcph.2000.6431
- Gabor Szegö, Orthogonal polynomials, American Mathematical Society Colloquium Publications, Vol. 23, American Mathematical Society, Providence, R.I., 1959. Revised ed. MR 0106295
- Ryszard Szwarc, Connection coefficients of orthogonal polynomials, Canad. Math. Bull. 35 (1992), no. 4, 548–556. MR 1191515, DOI 10.4153/CMB-1992-071-3
- Ryszard Szwarc, Connection coefficients of orthogonal polynomials with applications to classical orthogonal polynomials, Applications of hypergroups and related measure algebras (Seattle, WA, 1993) Contemp. Math., vol. 183, Amer. Math. Soc., Providence, RI, 1995, pp. 341–346. MR 1334788, DOI 10.1090/conm/183/02071
- D. Tchiotsop, D. Wolf, V. Louis-Dorr, and R. Husson, ECG data compression using Jacobi polynomials, Proceedings of the 29th Annual International Conference of the IEEE EMBS (Lyon France), 2007, pp. 1863–1867.
- Nico M. Temme, Special functions, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1996. An introduction to the classical functions of mathematical physics. MR 1376370, DOI 10.1002/9781118032572
- Alex Townsend, Marcus Webb, and Sheehan Olver, Fast polynomial transforms based on Toeplitz and Hankel matrices, Math. Comp. 87 (2018), no. 312, 1913–1934. MR 3787396, DOI 10.1090/mcom/3277
- F. G. Tricomi and A. Erdélyi, The asymptotic expansion of a ratio of gamma functions, Pacific J. Math. 1 (1951), 133–142. MR 43948
- Mark Tygert, Fast algorithms for spherical harmonic expansions. II, J. Comput. Phys. 227 (2008), no. 8, 4260–4279. MR 2403883, DOI 10.1016/j.jcp.2007.12.019
- Yuanzhe Xi and Jianlin Xia, On the stability of some hierarchical rank structured matrix algorithms, SIAM J. Matrix Anal. Appl. 37 (2016), no. 3, 1279–1303. MR 3549882, DOI 10.1137/15M1026195
- Yuanzhe Xi, Jianlin Xia, Stephen Cauley, and Venkataramanan Balakrishnan, Superfast and stable structured solvers for Toeplitz least squares via randomized sampling, SIAM J. Matrix Anal. Appl. 35 (2014), no. 1, 44–72. MR 3152737, DOI 10.1137/120895755
- Jianlin Xia, On the complexity of some hierarchical structured matrix algorithms, SIAM J. Matrix Anal. Appl. 33 (2012), no. 2, 388–410. MR 2970212, DOI 10.1137/110827788
- Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl. 17 (2010), no. 6, 953–976. MR 2759603, DOI 10.1002/nla.691
- Jianlin Xia, Yuanzhe Xi, and Ming Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl. 33 (2012), no. 3, 837–858. MR 3023454, DOI 10.1137/110831982
- Dongbin Xiu and George Em Karniadakis, Supersensitivity due to uncertain boundary conditions, Internat. J. Numer. Methods Engrg. 61 (2004), no. 12, 2114–2138. MR 2101601, DOI 10.1002/nme.1152
Additional Information
- Jie Shen
- Affiliation: Department of Mathematics, Purdue University, West Lafayette, Indiana 47907
- MR Author ID: 257933
- ORCID: 0000-0002-4885-5732
- Email: shen7@purdue.edu
- Yingwei Wang
- Affiliation: Department of Mathematics, University of Wisconsin-Madison, Madison, Wisconsin 53706
- MR Author ID: 858648
- Email: wywshtj@gmail.com
- Jianlin Xia
- Affiliation: Department of Mathematics, Purdue University, West Lafayette, Indiana 47907
- MR Author ID: 638529
- Email: xiaj@purdue.edu
- Received by editor(s): April 16, 2017
- Received by editor(s) in revised form: November 14, 2017, February 8, 2018, and April 11, 2018
- Published electronically: August 27, 2018
- Additional Notes: The work of the first author was partially supported by NSF grants DMS-1620262, DMS-1720442 and AFOSR FA9550-16-1-0102.
The research of the third author was supported in part by NSF CAREER Award DMS-1255416. - © Copyright 2018 American Mathematical Society
- Journal: Math. Comp. 88 (2019), 1743-1772
- MSC (2010): Primary 65T50, 65D05, 65N35, 65F30
- DOI: https://doi.org/10.1090/mcom/3377
- MathSciNet review: 3925483