A Fast Multipole Method based on Band-limited Approximations for Radial Basis Functions

Wei Zhao, Martin Stoll

Abstract

The meshless radial basis function (RBF) method is a powerful technique for interpolating scattered data. However, solving large-scale RBF interpolation problems is computationally expensive, requiring $\mathcal{O}(N^2)$ operations for $N$ points. While the Fast Multipole Method (FMM) can reduce this complexity, traditional implementations often rely on kernel-specific analytic expansions. This paper presents a novel kernel-independent FMM based on band-limited approximations and quadrature rules. By leveraging the Fourier transform of the RBF kernels, the method achieves $\mathcal{O}(N \log N)$ complexity for multilevel implementations, significantly extending the applicability of FMM to various RBF types.

Introduction: The Scalability Bottleneck

Radial Basis Functions (RBFs) are highly effective for interpolating scattered data due to their meshless nature, which avoids the need for complex grid generation in high-dimensional spaces or irregular geometries. Despite their flexibility, RBFs suffer from poor scalability. Calculating the interaction between $N$ points typically involves a direct summation that scales quadratically, making large-scale problems (e.g., $N > 10^6$) computationally prohibitive.

Definitions of standard Radial Basis Functions

Traditional Fast Multipole Methods (FMM) were designed to alleviate this "N-body" problem by approximating far-field interactions. However, many FMM variants require complex, kernel-specific mathematical expansions (such as Laurent series or spherical harmonics). This makes it difficult to switch between different kernels like Gaussians, Multiquadrics, or Thin-plate splines without significant re-derivation.

Methodology: Band-limited Approximations

The proposed method overcomes kernel dependency by shifting the problem into the frequency domain. The core of the approach involves three strategic steps:

  1. Mollification: The standard RBF kernel $\Phi$ is replaced with a "mollified" version $\Phi_\sigma$. This process creates a band-limited approximation where the Fourier transform is truncated or forced to zero beyond a specific bandwidth $\sigma$.
  2. Low-Rank Representation: Because the mollified kernel is band-limited, its inverse Fourier transform can be efficiently approximated using numerical quadrature. This represents the kernel as a finite sum of exponential functions, which naturally provides a low-rank structure.
  3. Diagonal Translation Operators: In the hierarchical tree structure of the FMM, information is moved between levels using translation operators. By using an exponential basis derived from the Fourier transform, these operators become diagonal matrices. This is a major efficiency gain over standard FMMs, where translations often involve dense matrix-vector multiplications.
Common RBFs and their corresponding Fourier transforms

As shown in the table above, the method relies on the analytical Fourier transform $\widehat{\Phi}(\xi)$ of the RBF. This allows the algorithm to remain "kernel-independent" as long as the Fourier transform is known or can be computed.

Key Insights and Performance

The "Fourier Shortcut" relies on the fact that smooth functions have rapidly decaying Fourier transforms. By slightly blurring the kernel through mollification, it can be represented by a small number of frequencies without sacrificing significant interpolation accuracy.

Numerical tests on synthetic scattered data and 1D boundary value problems (such as Poisson-like equations) demonstrate that the method successfully reduces computational complexity to $\mathcal{O}(N \log N)$ for the multilevel fast multipole method (MLFMM). Crucially, the accuracy remains comparable to direct RBF methods; for instance, in a test with $N=15$ points, the band-limited approximation achieved an RMS error of $7.28 \times 10^{-7}$, nearly identical to the standard RBF error of $1.01 \times 10^{-6}$.

Conclusion and Future Directions

This band-limited FMM provides a robust framework for scaling meshless interpolation. While the current implementation excels in 1D and 2D, future work will focus on addressing the "curse of dimensionality" in higher-dimensional quadrature rules and automating the selection of bandwidth parameters ($\sigma$) to optimize the trade-off between speed and precision.

Summary updated

Abstract

The meshless/meshfree radial basis function (RBF) method is a powerful technique for interpolating scattered data. But, solving large RBF interpolation problems without fast summation methods is computationally expensive. For RBF interpolation with $N$ points, using a direct method requires $\mathcal{O}(N^2)$ operations. As a fast summation method, the fast multipole method (FMM) has been implemented in speeding up the matrix-vector multiply, which reduces the complexity from $\mathcal{O}(N^2)$ to $\mathcal{O}(N^{1.5})$ and even to $\mathcal{O}(NlogN)$ for the multilevel fast multipole method (MLFMM). In this paper, we present a novel kernel-independent fast multipole method for RBF interpolation, which is used in combination with the evaluation of point-to-point interactions by RBF and the fast matrix-vector multiplication. This approach is based on band-limited approximation and quadrature rules, which extends the range of applicability of FMM.
BibTeX
@misc{zhao2016fast,
  author = {Wei Zhao and Martin Stoll},
  title = {{A Fast Multipole Method based on Band-limited Approximations for Radial Basis Functions}},
  year = {2016},
  eprint = {1606.07652},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.07652},
}
Figure