Adaptive radial basis function partition of unity interpolation: a bivariate algorithm for unstructured data. (English) Zbl 1467.65006
Summary: In this article we present a new adaptive algorithm for solving 2D interpolation problems of large scattered data sets through the radial basis function partition of unity method. Unlike other time-consuming schemes this adaptive method is able to efficiently deal with scattered data points with highly varying density in the domain. This target is obtained by decomposing the underlying domain in subdomains of variable size so as to guarantee a suitable number of points within each of them. The localization of such points is done by means of an efficient search procedure that depends on a partition of the domain in square cells. For each subdomain the adaptive process identifies a predefined neighborhood consisting of one or more levels of neighboring cells, which allows us to quickly find all the subdomain points. The algorithm is further devised for an optimal selection of the local shape parameters associated with radial basis function interpolants via leave-one-out cross validation and maximum likelihood estimation techniques. Numerical experiments show good performance of this adaptive algorithm on some test examples with different data distributions. The efficacy of our interpolation scheme is also pointed out by solving real world applications.
MSC:
| 65D05 | Numerical interpolation |
| 65D12 | Numerical radial basis function approximation |
| 65D15 | Algorithms for approximation of functions |
| 41A05 | Interpolation in approximation theory |
Keywords:
meshless approximation; partition of unity methods; radial basis functions; scattered data interpolation; adaptive algorithmsReferences:
| [1] | Allasia, G.; Cavoretto, R.; De Rossi, A., Hermite-Birkhoff interpolation on scattered data on the sphere and other manifolds, Appl. Math. Comput., 318, 35-50 (2018) · Zbl 1426.65011 |
| [2] | Arya, S.; Mount, D.; Netanyahu, N.; Silverman, R.; Wu, A., An optimal algorithm for approximate nearest neighbor searching in fixed dimensions, J. ACM, 45, 891-923 (1998) · Zbl 1065.68650 · doi:10.1145/293347.293348 |
| [3] | Babuška, I.; Melenk, JM, The partition of unity method, Int. J. Numer. Methods Eng., 40, 727-758 (1997) · Zbl 0949.65117 · doi:10.1002/(SICI)1097-0207(19970228)40:4<727::AID-NME86>3.0.CO;2-N |
| [4] | Ben-Ahmed, EH; Sadik, M.; Wakrim, M., Radial basis function partition of unity method for modelling water flow in porous media, Comput. Math. Appl., 75, 2925-2941 (2018) · Zbl 1415.76593 · doi:10.1016/j.camwa.2018.01.022 |
| [5] | Ben-Ahmed, EH; Sadik, M.; Wakrim, M., A stable radial basis function partition of unity method with d-rectangular patches for modelling water flow in porous media, J. Sci. Comput., 84, 18 (2020) · Zbl 1444.35059 · doi:10.1007/s10915-020-01273-2 |
| [6] | de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry (1997), Berlin: Springer, Berlin · Zbl 0877.68001 · doi:10.1007/978-3-662-03427-9 |
| [7] | Bozzini, M.; Lenarduzzi, L.; Rossini, M., Polyharmonic splines: An approximation method for noisy scattered data of extra-large size, Appl. Math. Comput., 216, 317-331 (2010) · Zbl 1186.65017 |
| [8] | Bracco, C.; Giannelli, C.; Sestini, A., Adaptive scattered data fitting by extension of local approximations to hierarchical splines, Comput. Aided Geom. Design, 52-53, 90-105 (2017) · Zbl 1366.65014 · doi:10.1016/j.cagd.2017.03.008 |
| [9] | Buhmann, MD, Radial Basis Functions: Theory and Implementation, Cambridge Monographs on Applied and Computational Mathematics (2003), Cambridge: Cambridge University Press, Cambridge · Zbl 1038.41001 · doi:10.1017/CBO9780511543241 |
| [10] | Cavoretto, R., A numerical algorithm for multidimensional modeling of scattered data points, Comput. Appl. Math., 34, 65-80 (2015) · Zbl 1314.65021 · doi:10.1007/s40314-013-0104-9 |
| [11] | Cavoretto, R.; De Rossi, A., A trivariate interpolation algorithm using a cube-partition searching procedure, SIAM J. Sci. Comput., 37, A1891-A1908 (2015) · Zbl 1327.65022 · doi:10.1137/140989157 |
| [12] | Cavoretto, R.; De Rossi, A., Adaptive meshless refinement schemes for RBF-PUM collocation, Appl. Math. Lett., 90, 131-138 (2019) · Zbl 1419.65132 · doi:10.1016/j.aml.2018.10.026 |
| [13] | Cavoretto, R.; De Rossi, A.; Perracchione, E., Optimal selection of local approximants in RBF-PU interpolation, J. Sci. Comput., 74, 1-22 (2018) · Zbl 1383.65010 · doi:10.1007/s10915-017-0418-7 |
| [14] | Davydov, O.; Zeilfelder, F., Scattered data fitting by direct extension of local polynomials to bivariate splines, Adv. Comput. Math., 21, 223-271 (2004) · Zbl 1065.41017 · doi:10.1023/B:ACOM.0000032041.68678.fa |
| [15] | Driscoll, T.; Heryudono, A., Adaptive residual subsampling methods for radial basis function interpolation and collocation problems, Comput. Math. Appl., 53, 927-939 (2007) · Zbl 1125.41005 · doi:10.1016/j.camwa.2006.06.005 |
| [16] | Fasshauer, G.; McCourt, M., Kernel-based Approximation Methods using Matlab, Interdisciplinary Mathematical Sciences (2015), Singapore: World Scientific, Singapore · Zbl 1318.00001 |
| [17] | Fasshauer, GE, Meshfree Approximation Methods with Matlab, Interdisciplinary Mathematical Sciences (2007), Singapore: World Scientific, Singapore · Zbl 1123.65001 |
| [18] | Fasshauer, GE, Positive definite kernels: Past, present and future, Dolomites Res. Notes Approx., 4, 21-63 (2011) |
| [19] | Fereshtian, A.; Mollapourasl, R.; Avram, F., RBF approximation by partition of unity for valuation of options under exponential L \(\acute{\text{e}}\) vy processes, J. Comput. Sci., 32, 44-55 (2019) · doi:10.1016/j.jocs.2019.02.008 |
| [20] | Fornberg, B.; Flyer, N., A Primer on Radial Basis Functions with Applications to the Geosciences (2015), Philadelphia: SIAM, Philadelphia · Zbl 1358.86001 · doi:10.1137/1.9781611974041 |
| [21] | Franke, R.; Hagen, H., Least squares surface approximation using multiquadrics and parametric domain distorsion, Comput. Aided Geom. Design, 16, 177-196 (1999) · Zbl 0914.68196 · doi:10.1016/S0167-8396(98)00043-0 |
| [22] | Gholampour, F.; Hesameddini, E.; Taleei, A., A stable RBF partition of unity local method for elliptic interface problems in two dimensions, Eng. Anal. Bound. Elem., 123, 220-232 (2021) · Zbl 1464.65202 · doi:10.1016/j.enganabound.2020.10.016 |
| [23] | Heryudono, A.; Larsson, E.; Ramage, A.; von Sydow, L., Preconditioning for radial basis function partition of unity methods, J. Sci. Comput., 67, 1089-1109 (2016) · Zbl 1342.65105 · doi:10.1007/s10915-015-0120-6 |
| [24] | Larsson, E.; Lehto, E.; Heryudono, A.; Fornberg, B., Stable computation of differentiation matrices and scattered node stencils based on gaussian radial basis functions, SIAM J. Sci. Comput., 35, A2096-A2119 (2013) · Zbl 1362.65026 · doi:10.1137/120899108 |
| [25] | Larsson, E.; Shcherbakov, V.; Heryudono, A., A least squares radial basis function partition of unity method for solving PDEs, SIAM J. Sci. Comput., 39, A2538-A2563 (2017) · Zbl 1377.65156 · doi:10.1137/17M1118087 |
| [26] | Lazzaro, D.; Montefusco, L., Radial basis functions for the multivariate interpolation of large scattered data sets, J. Comput. Appl. Math., 140, 521-536 (2002) · Zbl 1025.65015 · doi:10.1016/S0377-0427(01)00485-X |
| [27] | Melenk, JM; Babuška, I., The partition of unity finite element method: Basic theory and applications, Comput. Methods. Appl. Mech. Eng., 139, 289-314 (1996) · Zbl 0881.65099 · doi:10.1016/S0045-7825(96)01087-0 |
| [28] | Mollapourasl, R.; Fereshtian, A.; Li, H.; Lu, X., RBF-PU method for pricing options under the jump-diffusion model with local volatility, J. Comput. Appl. Math., 337, 98-118 (2018) · Zbl 1457.65148 · doi:10.1016/j.cam.2018.01.002 |
| [29] | Renka, R.; Brown, R., Algorithm 792: Accuracy tests of ACM algorithms for interpolation of scattered data in the plane, ACM Trans. Math. Softw., 25, 78-94 (1999) · Zbl 0963.65014 · doi:10.1145/305658.305745 |
| [30] | Rippa, S., An algorithm for selecting a good value for the parameter \(c\) in radial basis function interpolation, Adv. Comput. Math., 11, 193-210 (1999) · Zbl 0943.65017 · doi:10.1023/A:1018975909870 |
| [31] | Scheuerer, M., An alternative procedure for selecting a good value for the parameter c in RBF-interpolation, Adv. Comput. Math., 34, 105-126 (2011) · Zbl 1208.65022 · doi:10.1007/s10444-010-9146-3 |
| [32] | Scheuerer, M.; Schaback, R.; Schlather, M., Interpolation of spatial data: a stochastic or a deterministic problem?, Eur. J. Appl. Math., 24, 601-629 (2013) · Zbl 1426.62284 · doi:10.1017/S0956792513000016 |
| [33] | Shepard, D.: A two-dimensional interpolation function for irregularly-spaced data. In: ACM ’68: Proceedings of the 1968 - 23rd ACM national conference, pp. 517-524 (1968) |
| [34] | Uddin, M.; Ali, H.; Taufiq, M., On the approximation of a nonlinear biological population model using localized radial basis function method, Math. Comput. Appl., 24, 54 (2019) |
| [35] | Wendland, H.: Fast evaluation of radial basis functions: methods based on partition of unity. In: C.K. Chui, L.L. Schumaker, J. Stöckler (eds.) Approximation Theory X: Wavelets, Splines, and Applications, pp. 473-483. Vanderbilt University Press (2002) · Zbl 1031.65022 |
| [36] | Wendland, H., Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics (2005), Cambridge: Cambridge University Press, Cambridge · Zbl 1075.65021 |
| [37] | Wong, R.; Luk, W.; Heng, P., Sampling with Hammersley and Halton points, J. Graph. Tools, 2, 9-24 (1997) · doi:10.1080/10867651.1997.10487471 |
| [38] | Zhang, Q.; Zhao, Y.; Levesley, J., Adaptive radial basis function interpolation using an error indicator, Numer. Algorithms, 76, 441-471 (2017) · Zbl 1377.65017 · doi:10.1007/s11075-017-0265-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
