PetRBF — a parallel O(N) algorithm for radial basis function interpolation with Gaussians. We have developed a parallel algorithm for radial basis function (rbf) interpolation that exhibits O(N) complexity, requires O(N) storage, and scales excellently up to a thousand processes. The algorithm uses a gmres iterative solver with a restricted additive Schwarz method (rasm) as a preconditioner and a fast matrix-vector algorithm. Previous fast rbf methods — achieving at most O(NlogN) complexity — were developed using multiquadric and polyharmonic basis functions. In contrast, the present method uses Gaussians with a small variance with respect to the domain, but with sufficient overlap. This is a common choice in particle methods for fluid simulation, our main target application. The fast decay of the Gaussian basis function allows rapid convergence of the iterative solver even when the subdomains in the rasm are very small. At the same time we show that the accuracy of the interpolation can achieve machine precision. The present method was implemented in parallel using the petsc library (developer version). Numerical experiments demonstrate its capability in problems of rbf interpolation with more than 50 million data points, timing at 106 s (19 iterations for an error tolerance of 10− 15) on 1024 processors of a Blue Gene/L (700 MHz PowerPC processors). The parallel code is freely available in the open-source model.

References in zbMATH (referenced in 21 articles )

Showing results 1 to 20 of 21.
Sorted by year (citations)

1 2 next

  1. Deng, Hao; To, Albert C.: Reverse shape compensation via a gradient-based moving particle optimization method (2021)
  2. Sharma, Ashesh; Ananthan, Shreyas; Sitaraman, Jayanarayanan; Thomas, Stephen; Sprague, Michael A.: Overset meshes for incompressible flows: on preserving accuracy of underlying discretizations (2021)
  3. Chen, Chuanfa; Li, Yanyan; Yan, Changqing: A random features-based method for interpolating digital terrain models with high efficiency (2020)
  4. Le Borne, Sabine; Wende, Michael: Multilevel interpolation of scattered data using (\mathcalH)-matrices (2020)
  5. Robinson, Gregor; Grooms, Ian: A fast tunable blurring algorithm for scattered data (2020)
  6. Le Borne, Sabine: Factorization, symmetrization, and truncated transformation of radial basis function-GA stabilized Gaussian radial basis functions (2019)
  7. Le Borne, Sabine; Wende, Michael: Domain decomposition methods in scattered data interpolation with conditionally positive definite radial basis functions (2019)
  8. Le Borne, Sabine; Wende, Michael: Iterative solution of Saddle-point systems from radial basis function (RBF) interpolation (2019)
  9. Renaudeau, Julien; Malvesin, Emmanuel; Maerten, Frantz; Caumon, Guillaume: Implicit structural modeling by minimization of the bending energy with moving least squares functions (2019)
  10. Zaspel, Peter: Algorithmic patterns for (\mathcalH)-matrices on many-core processors (2019)
  11. Cuomo, Salvatore; Galletti, Ardelio; Giunta, Giulio; Marcellino, Livia: Reconstruction of implicit curves and surfaces via RBF interpolation (2017)
  12. Slattery, Stuart R.: Mesh-free data transfer algorithms for partitioned multiphysics problems: conservation, accuracy, and parallelism (2016)
  13. Farrell, Patricio; Pestana, Jennifer: Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs. (2015)
  14. Xiao, Jianping; Wang, Lei; Boyd, John P.: RBF-vortex methods for the barotropic vorticity equation on a sphere (2015)
  15. Torres, C. E.; Parishani, H.; Ayala, O.; Rossi, L. F.; Wang, L.-P.: Analysis and parallel implementation of a forced (N)-body problem (2013)
  16. Ward, John Paul: (L^p) error estimates for approximation by Sobolev splines and Wendland functions on (\mathbbR^d) (2013)
  17. Yokota, Rio; Barba, L. A.: FMM-based vortex method for simulation of isotropic turbulence on GPUs, compared with a spectral method (2013)
  18. Deng, Quan; Driscoll, Tobin A.: A fast treecode for multiquadric interpolation with varying shape parameters (2012)
  19. Yokota, Rio; Barba, L. A.: Comparing the treecode with FMM on GPUs for vortex particle simulations of a leapfrogging vortex ring (2011)
  20. Yokota, Rio; Barba, L. A.; Knepley, Matthew G.: PetRBF - A parallel (O(N)) algorithm for radial basis function interpolation with Gaussians (2010)

1 2 next