OpenCL Based Parallel Algorithm for RBF-PUM Interpolation

被引:29
作者
Cavoretto, Roberto [1 ]
Schneider, Teseo [2 ]
Zulian, Patrick [2 ]
机构
[1] Univ Torino, Dept Math G Peano, Via Carlo Alberto 10, I-10123 Turin, Italy
[2] Univ Svizzera Italiana, Fac Informat, Via Giuseppe Buffi 13, CH-6904 Lugano, Switzerland
基金
瑞士国家科学基金会;
关键词
Mesh-free approximation; Partition of unity methods; Radial basis functions; Scattered data interpolation; Parallel algorithms; Opencl; SCATTERED DATA; PARTITION; COMPUTATION;
D O I
10.1007/s10915-017-0431-x
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We present a parallel algorithm for multivariate Radial Basis Function Partition of Unity Method (RBF-PUM) interpolation. The concurrent nature of the RBF-PUM enables designing parallel algorithms for dealing with a large number of scattered data-points in high space dimensions. To efficiently exploit this concurrency, our algorithm makes use of shared-memory parallel processors through the OpenCL standard. This efficiency is achieved by a parallel space partitioning strategy with linear computational time complexity with respect to the input and evaluation points. The speed of our approach allows for computationally more intensive construction of the interpolant. In fact, the RBF-PUM can be coupled with a cross-validation technique that searches for optimal values of the shape parameters associated with each local RBF interpolant, thus reducing the global interpolation error. The numerical experiments support our claims by illustrating the interpolation errors and the running times of our algorithm.
引用
收藏
页码:267 / 289
页数:23
相关论文
共 46 条
[1]   A COMPARISON OF SHARED AND NONSHARED MEMORY MODELS OF PARALLEL COMPUTATION [J].
ANDERSON, RJ ;
SNYDER, L .
PROCEEDINGS OF THE IEEE, 1991, 79 (04) :480-487
[2]  
[Anonymous], 2008, 2008 IEEE Hot Chips 20 Symposium (HCS), DOI 10.1109/HOTCHIPS.2008.7476516
[3]  
[Anonymous], 2003, C MO AP C M, DOI 10.1017/CBO9780511543241
[4]  
[Anonymous], 2015, Kernel-based approximation methods using Matlab.
[5]  
Babuska I, 1997, INT J NUMER METH ENG, V40, P727, DOI 10.1002/(SICI)1097-0207(19970228)40:4<727::AID-NME86>3.0.CO
[6]  
2-N
[7]  
Board O., OPENMP FOR
[8]   Polyharmonic splines: An approximation method for noisy scattered data of extra-large size [J].
Bozzini, Mira ;
Lenarduzzi, Licia ;
Rossini, Milvia .
APPLIED MATHEMATICS AND COMPUTATION, 2010, 216 (01) :317-331
[9]  
Brent R. P., 2013, Algorithms for Minimization Without Derivatives
[10]  
Buttlar D.A., 1996, Pthreads Programming