Algorithm 840

Algorithm 840: Computation of grid points, quadrature weights and derivatives for spectral element methods using prolate spheroidal wave functions -- prolate elements High order domain decomposition methods using a basis of Legendre polynomials, known variously as “spectral elements” or “$p$-type finite elements”, have become very popular. Recent studies suggest that accuracy and efficiency can be improved by replacing Legendre polynomials by prolate spheroidal wave functions of zeroth order. In this article, we explain the practicalities of computing all the numbers needed to switch bases: the grid points $x_j$, the quadrature weights $w_j$, and the values of the prolate functions and their derivatives at the grid points. The prolate functions themselves are computed by a Legendre-Galerkin discretization of the prolate differential equation; this yields a symmetric tridiagonal matrix. The prolate functions are then defined by Legendre series whose coefficients are the eigenfunctions of the matrix eigenproblem. The grid points and weights are found simultaneously through a Newton iteration. For large $N$ and $c$, the iteration diverges from a first guess of the Legendre-Lobatto points and weights. Fortunately, the variations of the $x_j$ and $w_j$ with $c$ are well-approximated by a symmetric parabola over the whole range of interest. This makes it possible to bypass the continuation procedures of earlier authors. (Source:

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 19 articles , 1 standard article )

Showing results 1 to 19 of 19.
Sorted by year (citations)

  1. Hogan, Jeffrey A.; Lakey, Joseph D.: On the numerical evaluation of bandpass prolates. II (2017)
  2. Schmutzhard, Sebastian; Hrycak, Tomasz; Feichtinger, Hans G.: A numerical study of the Legendre-Galerkin method for the evaluation of the prolate spheroidal wave functions (2015)
  3. Hogan, Jeffrey A.; Kroger, James; Lakey, Joseph D.: Time and bandpass limiting and an application to EEG (2014)
  4. Wang, Li-Lian; Zhang, Jing; Zhang, Zhimin: On $hp$-convergence of prolate spheroidal wave functions and a new well-conditioned prolate-collocation scheme (2014)
  5. Hogan, Jeffrey A.; Lakey, Joseph D.: Letter to the editor: On the numerical evaluation of bandpass prolates (2013)
  6. Boyd, John P.: Numerical, perturbative and Chebyshev inversion of the incomplete elliptic integral of the second kind (2012)
  7. Kong, Wai Yip; Rokhlin, Vladimir: A new class of highly accurate differentiation schemes based on the prolate spheroidal wave functions (2012)
  8. Zhang, Jing; Wang, Lilian: On spectral approximations by generalized Slepian functions (2011)
  9. Zhang, Jing; Wang, Li-Lian; Rong, Zhijian: A prolate-element method for nonlinear PDEs on the sphere (2011)
  10. Žitňan, P.: The collocation solution of Poisson problems based on approximate Fekete points (2011)
  11. Wang, Li-Lian: Analysis of spectral approximations using prolate spheroidal wave functions (2010)
  12. Wang, Li-Lian; Zhang, Jing: A new generalization of the PSWFs with applications to spectral approximations on quasi-uniform grids (2010)
  13. Boyd, John P.: Large-degree asymptotics and exponential asymptotics for Fourier, Chebyshev and Hermite coefficients and Fourier transforms (2009)
  14. Huang, Chia-Chien: Semiconductor nanodevice simulation by multidomain spectral method with Chebyshev, prolate spheroidal and Laguerre basis functions (2009)
  15. Kovvali, Narayan; Lin, Wenbin; Zhao, Zhiqin; Couchman, Luise; Carin, Lawrence: Rapid prolate pseudospectral differentiation and interpolation with the fast multipole method (2006)
  16. Lin, Wenbin; Kovvali, Narayan; Carin, Lawrence: Pseudospectral method based on prolate spheroidal wave functions for semiconductor nanodevice simulation (2006)
  17. Taylor, Mark A.; Wingate, Beth A.: A generalization of prolate spheroidal functions with more uniform resolution to the triangle (2006)
  18. Boyd, John P.: Algorithm 840: Computation of grid points, quadrature weights and derivatives for spectral element methods using prolate spheroidal wave functions -- prolate elements (2005)
  19. Boyd, John P.: Prolate spheroidal wavefunctions as an alternative to Chebyshev and Legendre polynomials for spectral element and pseudospectral algorithms (2004)