LAUSR

Both barycentric Lagrange interpolation and barycentric rational interpolation are thought to be stable and effective methods for approximating a given function on some special point sets. A direct evaluation of these interpolants due to N interpolation points at M sampling points requires O(NM)$\mathcal {O}(NM)$ arithmetic operations. In this paper, we introduce two fast multipole methods to reduce the complexity to O(maxN,M)$\mathcal {O}(\max \left \{N,M\right \})$. The convergence analysis is also presented in this paper.