Fast algorithms for polynomial interpolation, integration, and differentiation

For functions tabulated at Chebyshev nodes on an interval, spectral interpolation and indefinite integration can be performed stably and efficiently via the fast Fourier transform. For many other sets of nodes (such as the Gaussian nodes on an interval) the classical interpolation and indefinite integration schemes are stable but slow, requiring O(N-2) arithmetic operations with N the number of nodes in the discretization of the interval. In this paper, a group of algorithms is presented for the efficient evaluation of Lagrange polynomial interpolants at multiple points on the line and for the rapid indefinite integration and differentiation of functions tabulated at nodes other than Chebyshev. The interpolation scheme requires O(N . log(1/epsilon)) arithmetic operations, and O(N . log N + N . log(1/epsilon)) operations are required for the integration and differentiation schemes, where epsilon is the precision of computations and N is the number of nodes (the interpolation and integration schemes are stable while the differentiation scheme has a condition number proportional to N-2). The algorithms utilize efficient versions of the fast multipole method which have been designed specifically for one-dimensional problems; these are also described in the present paper. Several experiments are included to illustrate the numerical performance of the approach.