February Fourier Talks 2007

Efficient O(NlogN) algorithms for interpolation

The talk is dedicated to a fast algorithm for interpolation of large sets of multidimensional data via radial basis functions (RBF). Recently Faul, Goodsell, and Powell (IMA, J. Numer. Anal. 25(2005), 1-24) presented a preconditioned Krylov subspace iterative algorithm for computing of coefficients of the RBF interpolant over N d-dimensional random data points. This algorithm appeared to be extremely robust to the distribution of the points and the iteration rapidly convergent. However, the iterative method has several steps whose computational and memory cost scales as O(N²), which prevents its use for large data sets. We developed O(N log N) algorithms for each of these steps, which brought the total memory and computational complexity to O(N log N) and successfully tested them for large data sets (up to million points in 2D and 3D). One of the presented algorithms accelerates solution of the computational geometry problem to construct the approximate cardinal function preconditioner. The other algorithm uses a novel version of the fast multipole method (FMM) to accelerate the matrix-vector product for polyharmonic kernels in 3D and multiquadric kernels in 2D.