James Bremer

Jhu Heitman, James Bremer, Vladimir Rokhlin

We observe that solutions of a large class of highly oscillatory second order linear ordinary differential equations can be approximated using nonoscillatory phase functions. In addition, we describe numerical experiments which illustrate important implications of this fact. For example, that many special functions of great interest --- such as the Bessel functions $J_ν$ and $Y_ν$ --- can be evaluated accurately using a number of operations which is $O(1)$ in the order $ν$. The present paper is devoted to the development of an analytical apparatus. Numerical aspects of this work will be reported at a later date.

James Bremer, Haizhao Yang

We describe a suite of fast algorithms for evaluating Jacobi polynomials, applying the corresponding discrete Sturm-Liouville eigentransforms and calculating Gauss-Jacobi quadrature rules. Our approach is based on the well-known fact that Jacobi's differential equation admits a nonoscillatory phase function which can be loosely approximated via an affine function over much of its domain. Our algorithms perform better than currently available methods in most respects. We illustrate this with several numerical experiments, the source code for which is publicly available.

James Bremer, Vladimir Rokhlin

We express a certain complex-valued solution of Legendre's differential equation as the product of an oscillatory exponential function and an integral involving only nonoscillatory elementary functions. By calculating the logarithmic derivative of this solution, we show that Legendre's differential equation admits a nonoscillatory phase function. Moreover, we derive from our expression an asymptotic expansion useful for evaluating Legendre functions of the first and second kinds of large orders, as well as the derivative of the nonoscillatory phase function. Numerical experiments demonstrating the properties of our asymptotic expansion are presented.

Xinge Zhang, James Bremer

The standard algorithm for the numerical evaluation of the prolate spheroidal wave function $\mathsf{Ps}\hskip.05em{}_{n}(x;γ^2)$ of order $0$, bandlimit $γ> 0$ and characteristic exponent $n$ has running time which grows with both $n$ and $γ$. Here, we describe an alternate approach which runs in time independent of these quantities. We present the results of numerical experiments demonstrating the properties of our scheme, and we have made our implementation of it publicly available.

James Bremer

We describe a method for the numerical evaluation of normalized versions of the associated Legendre functions $P_ν^{-μ}$ and $Q_ν^{-μ}$ of degrees $0 \leq ν\leq 1,000,000$ and orders $-ν\leq μ\leq ν$ on the interval $(-1,1)$. Our algorithm, which runs in time independent of $ν$ and $μ$, is based on the fact that while the associated Legendre functions themselves are extremely expensive to represent via polynomial expansions, the logarithms of certain solutions of the differential equation defining them are not. We exploit this by numerically precomputing the logarithms of carefully chosen solutions of the associated Legendre differential equation and representing them via piecewise trivariate Chebyshev expansions. These precomputed expansions, which allow for the rapid evaluation of the associated Legendre functions over a large swath of parameter domain mentioned above, are supplemented with asymptotic and series expansions in order to cover it entirely. The results of numerical experiments demonstrating the efficacy of our approach are presented, and our code for evaluating the associated Legendre functions is publicly available.

James Bremer

We describe a method for the rapid numerical evaluation of the Bessel functions of the first and second kinds of nonnegative real orders and positive arguments. Our algorithm makes use of the well-known observation that although the Bessel functions themselves are expensive to represent via piecewise polynomial expansions, the logarithms of certain solutions of Bessel's equation are not. We exploit this observation by numerically precomputing the logarithms of carefully chosen Bessel functions and representing them with piecewise bivariate Chebyshev expansions. Our scheme is able to evaluate Bessel functions of orders between $0$ and $1\sep,000\sep,000\sep,000$ at essentially any positive real argument. In that regime, it is competitive with existing methods for the rapid evaluation of Bessel functions and has several advantages over them. First, our approach is quite general and can be readily applied to many other special functions which satisfy second order ordinary differential equations. Second, by calculating the logarithms of the Bessel functions rather than the Bessel functions themselves, we avoid many issues which arise from numerical overflow and underflow. Third, in the oscillatory regime, our algorithm calculates the values of a nonoscillatory phase function for Bessel's differential equation and its derivative. These quantities are useful for computing the zeros of Bessel functions, as well as for rapidly applying the Fourier-Bessel transform. The results of extensive numerical experiments demonstrating the efficacy of our algorithm are presented. A Fortran package which includes our code for evaluating the Bessel functions as well as our code for all of the numerical experiments described here is publically available.

James Bremer

We describe a method for calculating the roots of special functions satisfying second order linear ordinary differential equations. It exploits the recent observation that the solutions of a large class of such equations can be represented via nonoscillatory phase functions, even in the high-frequency regime. Our algorithm achieves near machine precision accuracy and the time required to compute one root of a solution is independent of the frequency of oscillations of that solution. Moreover, despite its great generality, our approach is competitive with specialized, state-of-the-art methods for the construction of Gaussian quadrature rules of large orders when it used in such a capacity. The performance of the scheme is illustrated with several numerical experiments and a Fortran implementation of our algorithm is available at the author's website.

James Bremer

We describe an algorithm for the numerical solution of second order linear differential equations in the highly-oscillatory regime. It is founded on the recent observation that the solutions of equations of this type can be accurately represented using nonoscillatory phase functions. Unlike standard solvers for ordinary differential equations, the running time of our algorithm is independent of the frequency of oscillation of the solutions. We illustrate the performance of the method with several numerical experiments.

Jhu Heitman, James Bremer, Vladimir Rokhlin et al.

We introduce a version of the asymptotic expansions for Bessel functions $J_ν(z)$, $Y_ν(z)$ that is valid whenever $|z| > ν$ (which is deep in the Fresnel regime), as opposed to the standard expansions that are applicable only in the Fraunhofer regime (i.e. when $|z| > ν^2$). As expected, in the Fraunhofer regime our asymptotics reduce to the classical ones. The approach is based on the observation that Bessel's equation admits a non-oscillatory phase function, and uses classical formulas to obtain an asymptotic expansion for this function; this in turn leads to both an analytical tool and a numerical scheme for the efficient evaluation of $J_ν(z)$, $Y_ν(z)$, as well as various related quantities. The effectiveness of the technique is demonstrated via several numerical examples. We also observe that the procedure admits far-reaching generalizations to wide classes of second order differential equations, to be reported at a later date.