Fast evaluation of vector splines in three dimensions

Vector spline techniques have been developed as general-purpose methods for vector field reconstruction. However, such vector splines involve high com putational complexity, which precludes applications of this technique to ma ny problems using large data sets. In this paper, we develop a fast multipo le method for the rapid evaluation of the vector spline in three dimensions . The algorithm depends on a tree-data structure and two hierarchical appro ximations: an upward multipole expansion approximation and a downward local Taylor series approximation. In comparison with the CPU time of direct cal culation, which increases at a quadratic rate with the number of points, th e presented fast algorithm achieves a higher speed in evaluation at a linea r rate. The theoretical error bounds are derived to ensure that the fast me thod works well with a specific accuracy. Numerical simulations are perform ed in order to demonstrate the speed and the accuracy of the proposed fast method.