Answers are grounded in this paper and cite their sources.
We consider a preconditioned Krylov subspace iterative algorithm presented by Faul, Goodsell, and Powell (IMA J. Numer. Anal. 25 (2005), pp. 1–24) for computing the coefficients of a radial basis function interpolant over N data points. This preconditioned Krylov iteration has been demonstrated 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 costs scale as O(N²), both in preliminary computations that compute the preconditioner and in the matrix-vector product involved in each step of the iteration. We effectively accelerate the iterative method to achieve an overall cost of O(Nlog N). The matrix vector product is accelerated via the use of the fast multipole method. The preconditioner requires the computation of a set of closest points to each point. We develop an O(Nlog N) algorithm for this step as well. Results are presented for multiquadric interpolation in R² and biharmonic interpolation in R³. A novel FMM algorithm for the evaluation of sums involving multiquadric functions in R² is presented as well.
No takes yet. Share an insight, caveat, or question.
Gumerov et al. (2007) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: