×

On the evaluation of prolate spheroidal wave functions and associated quadrature rules. (English) Zbl 1302.65061

From the summary: As demonstrated by Slepian et al. in a sequence of classical papers (see the references), prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. Recently, PSWFs have been becoming increasingly popular in various areas in which such functions occur – this includes physics (e.g. wave phenomena, fluid dynamics), engineering (signal processing, filter design), etc.
To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of corresponding quadrature rules, interpolation formulas, etc. During the last 15 years, substantial progress has been made in the design of such algorithms (see the references).The complexity of many of the existing algorithms, however, is at least quadratic in the band limit \(c\). For example, the evaluation of the \(n\)th eigenvalue of the prolate integral operator requires \(O(c^2+n^2)\) operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit \(c\) requires \(O(c^3)\) operations. Therefore, while the existing algorithms are satisfactory for moderate values of \(c\) (e.g. \(c\leqslant 10^3\)), they tend to be relatively slow when \(c\) is large (e.g. \(c\geqslant 10^4\)).
In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. While the analysis is somewhat involved and will be published separately, the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the \(n\)th eigenvalue of the prolate integral operator requires \(O(n+c\cdot\log c)\) operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit \(c\) requires \(O(c)\) operations. All algorithms described in this paper produce results essentially to machine precision. Our results are illustrated via several numerical experiments.

MSC:

65D20 Computation of special functions and constants, construction of tables
94A11 Application of orthogonal and other special functions
33F05 Numerical approximation and evaluation of special functions
41A55 Approximate quadratures
42A10 Trigonometric approximation
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Abramowitz, M.; Stegun, I. A., Handbook of mathematical functions with formulas, graphs and mathematical tables, (1964), Dover Publications · Zbl 0171.38503
[2] Barth, W.; Martin, R. S.; Wilkinson, J. H., Calculation of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection, Numer. Math., 9, 386-393, (1967) · Zbl 0189.47803
[3] Beylkin, G.; Monzon, L., On generalized Gaussian quadratures for exponentials and their applications, Appl. Comput. Harmon. Anal., 12, 332-373, (2002) · Zbl 1015.65012
[4] Beylkin, G.; Monzon, L., On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal., 19, 17-48, (2005) · Zbl 1075.65022
[5] Birkhoff, G.; Rota, G.-C., Ordinary differential equations, (1978), Wiley · Zbl 0183.35601
[6] Bouwkamp, C. J., On spheroidal wave functions of order zero, J. Math. Phys., 26, 79-92, (1947) · Zbl 0033.12104
[7] Bremer, J.; Gimbutas, Z.; Rokhlin, V., A nonlinear optimization procedure for generalized Gaussian quadratures, SIAM J. Sci. Comput., 32, 4, 1761-1788, (2010) · Zbl 1215.65045
[8] Cheng, H.; Yarvin, N.; Rokhlin, V., Non-linear optimization, quadrature and interpolation, SIAM J. Optim., 9, 901-923, (1999) · Zbl 1032.90528
[9] Dahlquist, G.; Björk, A., Numerical methods, (1974), Prentice Hall
[10] Fedoryuk, M. V., Asymptotic analysis of linear ordinary differential equations, (1993), Springer-Verlag Berlin
[11] Flammer, C., Spheroidal wave functions, (1956), Stanford University Press Stanford, CA
[12] Glaser, Andreas; Liu, Xiangtao; Rokhlin, Vladimir, A fast algorithm for the calculation of the roots of special functions, SIAM J. Sci. Comput., 29, 4, 1420-1438, (2007), (electronic) · Zbl 1145.65015
[13] Gradshteyn, I. S.; Ryzhik, I. M., Table of integrals, series, and products, (2007), Elsevier · Zbl 1208.65001
[14] Hodge, D. B., Eigenvalues and eigenfunctions of the spheroidal wave equation, J. Math. Phys., 11, 2308-2312, (1970) · Zbl 0219.65039
[15] Isaacson, E.; Keller, H. B., Analysis of numerical methods, (1966), Wiley New York · Zbl 0168.13101
[16] Karlin, S.; Studden, W. J., Tchebycheff systems with applications in analysis and statistics, (1966), Wiley-Interscience New York · Zbl 0153.38902
[17] Krein, M. G., The ideas of P.L. Chebyshev and A.A. Markov in the theory of limiting values of integrals, Amer. Math. Soc. Transl., 12, 1-122, (1959)
[18] Landau, H. J.; Pollak, H. O., Prolate spheroidal wave functions, Fourier analysis, and uncertainty - II, Bell Syst. Tech. J., 40, 65-84, (1961) · Zbl 0184.08602
[19] Landau, H. J.; Widom, H., Eigenvalue distribution of time and frequency limiting, J. Math. Anal. Appl., 77, 469-481, (1980) · Zbl 0471.47029
[20] Ma, J.; Rokhlin, V.; Wandzura, S., Generalized Gaussian quadratures for systems of arbitrary functions, SIAM J. Numer. Anal., 33, 971-996, (1996) · Zbl 0858.65015
[21] Markov, A. A., On the limiting values of integrals in connection with interpolation, Zap. Imp. Akad. Nauk Fiz.-Mat. Otd., 6(8), 5, (1898), (in Russian)
[22] Markov, A. A., Selected papers on continued fractions and the theory of functions deviating least from zero, (1948), OGIZ Moscow, (in Russian)
[23] Miller, Richard K.; Michel, Anthony N., Ordinary differential equations, (1982), Dover Publications · Zbl 0552.34001
[24] Morse, P. M.; Feshbach, H., Methods of theoretical physics, (1953), McGraw-Hill New York · Zbl 0051.40603
[25] Osipov, A., Certain inequalities involving prolate spheroidal wave functions and associated quantities, Appl. Comput. Harmon. Anal., (2012), in press · Zbl 1296.65039
[26] Osipov, A., Certain upper bounds on the eigenvalues associated with prolate spheroidal wave functions, Appl. Comput. Harmon. Anal., (2013), in press · Zbl 1302.42039
[27] Osipov, A.; Rokhlin, V., Detailed analysis of prolate quadratures and interpolation formulas, (2012)
[28] Osipov, A., Evaluation of small elements of the eigenvectors of certain symmetric tridiagonal matrices with high relative accuracy, (2012)
[29] Papoulis, A., Signal analysis, (1977), McGraw-Hill · Zbl 0422.94001
[30] Rokhlin, V.; Tygert, M., Fast algorithms for spherical harmonic expansions, SIAM J. Sci. Comput., 27, 6, 1903-1928, (2006) · Zbl 1104.65134
[31] Rokhlin, V.; Xiao, H., Approximate formulae for certain prolate spheroidal wave functions valid for large value of both order and band limit, Appl. Comput. Harmon. Anal., 22, 105-123, (2007) · Zbl 1110.41010
[32] Rudin, W., Real and complex analysis, (1970), McGraw-Hill
[33] Slepian, D., Some comments on Fourier analysis, uncertainty, and modeling, SIAM Rev., 3, 379-393, (1983) · Zbl 0571.94004
[34] Slepian, D.; Pollak, H. O., Prolate spheroidal wave functions, Fourier analysis, and uncertainty - I, Bell Syst. Tech. J., 40, 43-64, (1961) · Zbl 0184.08601
[35] Slepian, D.; Pollak, H. O., Prolate spheroidal wave functions, Fourier analysis, and uncertainty - IV: extensions to many dimensions, generalized prolate spheroidal wave functions, Bell Syst. Tech. J., 43, 3009-3057, (1964) · Zbl 0184.08604
[36] Slepian, D., Some asymptotic expansions for prolate spheroidal wave functions, J. Math. Phys., 44, 99-140, (1965) · Zbl 0128.29601
[37] Shkolnisky, Y., Prolate spheroidal wave functions on a disc - integration and approximation of two-dimensional bandlimited functions, Appl. Comput. Harmon. Anal., 22, 2, 235-256, (2007) · Zbl 1117.65041
[38] Tygert, M., Fast algorithms for spherical harmonic expansions II, J. Comput. Phys., 227, 4260-4279, (2008) · Zbl 1147.65111
[39] Wilkinson, J. H., Algebraic eigenvalue problem, (1965), Oxford University Press New York · Zbl 0258.65037
[40] Xiao, H.; Rokhlin, V.; Yarvin, N., Prolate spheroidal wavefunctions, quadrature and interpolation, Inverse Problems, 17, 4, 805-828, (2001) · Zbl 0991.65024
[41] Yarvin, N.; Rokhlin, V., Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput., 20, 699-718, (1998) · Zbl 0932.65020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.