An O(1) Algorithm for the Numerical Evaluation of the Prolate Spheroidal Wave Functions of Order 0

The standard algorithm for the numerical evaluation of the prolate spheroidal wave function $\mathsf{P}\mathsf{s}{}_n(x;{\gamma }^2)$ of order $0$, bandlimit $\gamma >0$ and characteristic exponent $n$ has running time which grows with both $n$ and $\gamma$. 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.