# February Fourier Talks 2007

## Nail Gumerov

### Title:

Efficient O(NlogN) algorithms for interpolation

### Abstract:

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^{2}), 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.