Fast multipole methods for approximating a function from sampling values (Q1681777)

In the paper, two fast multipole methods for approximating a given function by means of barycentric Lagrange interpolation and barycentric rational interpolation on \(N\) interpolation points at \(M\) sampling points are described. The set of interpolation points represents the source domain for interpolation, the set of sampling points represents the target domain. Compared to the numerical complexity \(O(NM)\) of the direct calculation of these interpolants, the complexity of the proposed methods is reduced to \(O(\max\{N,M\})\). Both methods are described in detail including the convergence analysis. A efficiency and accuracy of the two multipole methods is demonstrated on several examples. The comparison of maximum relative errors between the two suggested methods and the direct evaluation of barycentric Lagrange interpolation and barycentric rational interpolation is presented. The suggested methods can be used in many applications such as differentiation, integration, rootfinding, statistics, etc.