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).
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
random data points. This algorithm appeared to be extremely robust
the distribution of the points and the iteration rapidly convergent.
However, the iterative method has several steps whose computational
memory cost scales as O(N2), which prevents its use for large
sets. We developed O(N log N) algorithms for each of these steps,
brought the total memory and computational complexity to O(N log N)
successfully tested them for large data sets (up to million points
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
fast multipole method (FMM) to accelerate the matrix-vector product
polyharmonic kernels in 3D and multiquadric kernels in 2D.