Fast structured Jacobi-Jacobi transforms

Shen, Jie; Wang, Yingwei; Xia, Jianlin

doi:10.1090/mcom/3377

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