FAST ALGORITHMS FOR POLYNOMIAL INTERPOLATION, INTEGRATION, AND DIFFERENTIATION

For functions tabulated at Chebyshev nodes on an interval, spectral in terpolation and indefinite integration can be performed stably and eff iciently via the fast Fourier transform. For many other sets of nodes (such as the Gaussian nodes on an interval) the classical interpolatio n and indefinite integration schemes are stable but slow, requiring O( N-2) arithmetic operations with N the number of nodes in the discretiz ation of the interval. In this paper, a group of algorithms is present ed 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 Chebysh ev. The interpolation scheme requires O(N . log(1/epsilon)) arithmetic operations, and O(N . log N + N . log(1/epsilon)) operations are requ ired for the integration and differentiation schemes, where epsilon is the precision of computations and N is the number of nodes (the inter polation and integration schemes are stable while the differentiation scheme has a condition number proportional to N-2). The algorithms uti lize efficient versions of the fast multipole method which have been d esigned specifically for one-dimensional problems; these are also desc ribed in the present paper. Several experiments are included to illust rate the numerical performance of the approach.