Fast radial basis function interpolation with Gaussians by localization and iteration

C Torres, LA Barba

Research output: Contribution to journalArticle (Academic Journal)


Radial basis function (RBF) interpolation is a technique for representing a function starting with data on scattered points. In the vortex particle method for solving the Navier–Stokes equations, the representation of the field of interest (the fluid vorticity) as a sum of Gaussians is like an RBF approximation. In this application, there are two instances when one may need to solve an RBF interpolation problem: upon initialization of the vortex particles, and after spatial adaptation to replace a set of disordered particles by another set with a more regular distribution. Solving large RBF interpolation problems is notoriously difficult with basis functions of global support, due to the need to solve a linear system with a fully populated and badly conditioned matrix. In the vortex particle method, in particular, one uses Gaussians of very small spread, which lead us to formulate a method of solution consisting of localization of the global problem, and improvement of solutions over iterations. It can be thought of as an opposite approach from the use of compact support basis functions to ease the solution procedure. Compact support bases result in sparse matrices, but at the cost of reduced approximation qualities. Instead, we keep the global basis functions, but localize their effect during the solution procedure, then add back the global effect of the bases via the iterations. Numerical experiments show that convergence is always obtained when the localized domains overlap via a buffer layer, and the particles overlap moderately. Algorithmic efficiency is excellent, achieving convergence to almost machine precision very rapidly with well-chosen parameters. We also discuss the complexity of the method and show that it can scale as O(N) for N particles.
Translated title of the contributionFast radial basis function interpolation with Gaussians by localization and iteration
Original languageEnglish
Pages (from-to)4976 - 4999
Number of pages24
JournalJournal of Computational Physics
Volume228, issue 14
Publication statusPublished - Aug 2009

Bibliographical note

Publisher: Elsevier

Fingerprint Dive into the research topics of 'Fast radial basis function interpolation with Gaussians by localization and iteration'. Together they form a unique fingerprint.

Cite this