We propose a new approach for the radial basis function (RBF) interpolation of large scattered data sets. It uses the space subdivision technique into independent cells allowing processing of large data sets with low memory requirements and offering high computation speed, together with the possibility of parallel processing as each cell can be processed independently. The proposed RBF interpolation was tested on both synthetic and real data sets. It proved its simplicity, robustness and the ability to handle large data sets together with significant speed-up. In the case of parallel processing, speed-up was experimentally proved when 2 and 4 threads were used.
DavisPJ. Interpolation and approximation. Courier Corporation1975.
2.
O’RourkeJMallinckrodtAJ, et al. Computational geometry in C. Computers in Physics1995; 9(1): 55-55.
3.
YangJWangZZhuCPengQ. Implicit surface reconstruction with radial basis functions. International Conference on Computer Vision and Computer Graphics, Springer2007; 5-12.
OhtakeYBelyaevAGSeidelH. A multi-scale approach to 3D scattered data interpolation with compactly supported basis function. 2003 International Conference on Shape Modeling and Applications (SMI 2003)2003; 153-164, 292.
6.
YokotaRBarbaLAKnepleyMG. PetRBF-A parallel O(N) algorithm for radial basis function interpolation with Gaussians. Computer Methods in Applied Mechanics and Engineering2010; 199(25): 1793-1804.
7.
SaadYSchultzMH. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing1986; 7(3): 856-869.
8.
CaiXCSarkisM. A restricted additive Schwarz preconditioner for general sparse linear systems. SIAM Journal on Scientific Computing1999; 21(2): 792-797.
9.
CuomoSGallettiAGiuntaGStaraceA. Surface reconstruction from scattered point via RBF interpolation on GPU. Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on IEEE2013; 433-440.
10.
SüßmuthJMeyerQGreinerG. Surface reconstruction based on hierarchical floating radial basis functions. Computer Graphics Forum2010; 29(6): 1854-1864.
11.
HaaseGMartinDOffnerG. Towards RBF Interpolation on Heterogeneous HPC Systems. Large-Scale Scientific Computing – 10th International Conference, LSSC2015; 2015: 182-190.
12.
BeatsonRKLightWABillingsSD. Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods. SIAM J Scientific Computing2001; 22(5): 1717-1740.
13.
FarrellPPestanaJ. Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs. Numerical Lin Alg with Applic2015; 22(4): 731-747.
14.
LingLKansaEJ. Preconditioning for radial basis functions with domain decomposition methods. Mathematical and Computer Modelling2004; 40(13): 1413-1427.
15.
MajdisovaZSkalaV. A radial basis function approximation for large datasets. Proceedings of SIGRAD2016; (127): 9-14.
16.
SmolikMSkalaVNedvedO. A Comparative Study of LOWESS and RBF Approximations for Visualization. Computational Science and Its Applications – ICCSA 2016 – 16th International Conference, Part II2016; 405-419.
BuiTQNguyenTNNguyen-DangH. A moving Kriging interpolation-based meshless method for numerical simulation of Kirchhoff plate problems. International Journal for Numerical Methods in Engineering2009; 77(10): 1371-1395.
19.
MaYZRoyerJJWangHWangYZhangT. Factorial kriging for multiscale modelling. Journal of the Southern African Institute of Mining and Metallurgy2014; 114(8): 651-659.
20.
KnopfGKSangoleA. Interpolating scattered data using 2D self-organizing feature maps. Graphical Models2004; 66(1): 50-69.
21.
MarinovMKobbeltL. Optimization methods for scattered data approximation with subdivision surfaces. Graphical Models2005; 67(5): 452-473.
LounsberyMDeRoseTDWarrenJ. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics (TOG)1997; 16(1): 34-73.
24.
EckMDeRoseTDuchampTHoppeHLounsberyMStuetzleW. Multiresolution analysis of arbitrary meshes. Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques ACM1995; 173-182.
25.
PanRSkalaV. A two-level approach to implicit surface modeling with compactly supported radial basis functions. Engineering with Computers2011; 27(3): 299-307.
26.
FasshauerGE. Meshfree approximation methods with MATLAB. vol. 6. World Scientific; 2007.
27.
SkalaV. Meshless interpolations for computer graphics, visualization and games. Eurographics 2015 – Tutorials2015.
28.
LarssonEFornbergB. A numerical study of some radial basis function based solution methods for elliptic PDEs. Computers & Mathematics with Applications2003; 46(5): 891-902.
29.
ZhangXSongKZLuMWLiuX. Meshless methods based on collocation with radial basis functions. Computational Mechanics2000; 26(4): 333-343.
30.
UhlirKSkalaV. Reconstruction of damaged images using radial basis functions. Signal Processing Conference, 2005 13th European, IEEE2005; 1-4.
31.
KarimAAdeliH. Radial basis function neural network for work zone capacity and queue estimation. Journal of Transportation Engineering2003; 129(5): 494-503.
32.
Ghosh-DastidarSAdeliHDadmehrN. Principal component analysis-enhanced cosine radial basis function neural network for robust epilepsy and seizure detection. IEEE Transactions on Biomedical Engineering2008; 55(2): 512-518.
33.
YingweiLSundararajanNSaratchandranP. Performance evaluation of a sequential minimal radial basis function (RBF) neural network learning algorithm. IEEE Transactions on Neural Networks1998; 9(2): 308-318.
34.
AdeliHKarimA. Fuzzy-wavelet RBFNN model for freeway incident detection. Journal of Transportation Engineering2000; 126(6): 464-471.
35.
KarimAAdeliH. Comparison of fuzzy-wavelet radial basis function neural network freeway incident detection model with California algorithm. Journal of Transportation Engineering2002; 128(1): 21-30.
36.
HsuCFLinCMYehRG. Supervisory adaptive dynamic RBF-based neural-fuzzy control system design for unknown nonlinear systems. Applied Soft Computing2013; 13(4): 1620-1626.
37.
MajdisovaZSkalaV. Big geo data surface approximation using radial basis functions: A comparative study. Computers & Geosciences2017; 109: 51-58.
38.
PrakashGKulkarniMSripatiU. Using RBF Neural Networks and Kullback-Leibler distance to classify channel models in Free Space Optics. Optical Engineering (ICOE), 2012 International Conference on IEEE2012; 1-6.
39.
SchagenIP. Interpolation in two dimensions – a new technique. IMA Journal of Applied Mathematics1979; 23(1): 53-59.
40.
FornbergBPiretC. On choosing a radial basis function and a shape parameter when solving a convective PDE on a sphere. J Comput Physics2008; 227(5): 2758-2780.
41.
MajdisovaZSkalaV. Radial basis function approximations: Comparison and applications. Applied Mathematical Modelling2017; 51: 728-743.
42.
SkalaV. RBF interpolation with CSRBF of large data sets. Procedia Computer Science2017; 108: 2433-2437.
43.
WendlandH. Computational aspects of radial basis function approximation. Studies in Computational Mathematics2006; 12: 231-256.
44.
HardyRL. Multiquadric equations of topography and other irregular surfaces. Journal of Geophysical Research1971; 76(8): 1905-1915.
45.
BellNGarlandM. Implementing sparse matrix-vector multiplication on throughput-oriented processors. Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, ACM2009; 18: 1-11.
46.
SimecekI. Sparse matrix computations using the quadtree storage format. Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2009 11th International Symposium on IEEE2009; 168-173.
47.
GilbertJRMolerCSchreiberR. Sparse matrices in MATLAB: Design and implementation. SIAM Journal on Matrix Analysis and Applications1992; 13(1): 333-356.
48.
SmolikMSkalaV. Vector Field Interpolation with Radial Basis Functions. Proceedings of SIGRAD 2016, Linköping University Electronic Press2016; (127): 15-21.
49.
SmolikMSkalaV. Classification of Critical Points Using a Second Order Derivative. Procedia Computer Science2017; 108: 2373-2377.
