Algorithm 840: computation of grid points, quadrature weights and derivatives for spectral element methods using prolate spheroidal wave functions---prolate elements

ABSTRACT

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.

REFERENCES

• 1: Bouwkamp, C. J. 1947. On spheroidal wave functions of order zero. J. Math. Phys. 26, 79--92.
• 2: John P. Boyd, A correction to the paper “Traps and snares in eigenvalue calculations with application to pseudospectral computations of ocean tides in a basin bounded by meridians”, Journal of Computational Physics, v.136 n.1, p.227-228, Sept. 1, 1997 [doi>10.1006/jcph.1997.5753]
• 3: Boyd, J. P. 2001. Chebyshev and Fourier Spectral Methods, 2d ed. Dover, Mineola, New York. 665 pp.
• 4: John P. Boyd, Prolate spheroidal wavefunctions as an alternative to Chebyshev and Legendre polynomials for spectral element and pseudospectral algorithms, Journal of Computational Physics, v.199 n.2, p.688-716, 20 September 2004 [doi>10.1016/j.jcp.2004.03.010]
• 5: Canuto, C., Hussaini, M. Y., Quarteroni, A., and Zang, T. A. 1988. Spectral Methods for Fluid Dynamics. Springer-Verlag, New York.
• 6: Q.-Y. Chen , D. Gottlieb , J. S. Hesthaven, Spectral Methods Based on Prolate Spheroidal Wave Functions for Hyperbolic PDEs, SIAM Journal on Numerical Analysis, v.43 n.5, p.1912-1933, 2005 [doi>10.1137/S0036142903432425]
• 7: Dennis, Jr., J. E. and Schnabel, R. B. 1983. Numerical Methods for Nonlinear Equations and Unconstrained Optimization. Prentice-Hall, Englewood Cliffs, New Jersey.
• 8: Deville, M. O., Fischer, P. F., and Mund, E. H. 2002. High-Order Methods for Incompressible Fluid Flow. Cambridge Monographs on Applied and Computational Mathematics, vol. 9. Cambridge University Press, Cambridge.
• 9: Karniadakis, G. E. and Sherwin, S. J. 1999. Spectral/hp Element Methods for CFD. Oxford University Press, Oxford. 448 pp.
• 10: Kelley, C. T. 2003. Solving Nonlinear Equations with Newton's Method. Fundamentals of Algorithms, vol. 1. Society for Industrial and Applied Mathematics, Philadelphia.
• 11: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 12: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 13: J. A. Weideman , S. C. Reddy, A MATLAB differentiation matrix suite, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.465-519, Dec. 2000 [doi>10.1145/365723.365727]
• 14: Xiao, H., Rokhlin, V., and Yarvin, N. 2001. Prolate spheroidal wavefunctions, quadrature and interpolation. Inverse Problems 17, 805--838.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Gaussian quadrature
      G.1.8 Partial Differential Equations
          Subjects: Spectral methods; Finite element methods
  G.4 MATHEMATICAL SOFTWARE

Keywords:
p-finite elements, Prolate spheroidal wavefunctions, prolate element method, spectral elements