A trivariate interpolation algorithm using a cube-partition searching procedure. (English) Zbl 1327.65022
Summary: In this paper we propose a fast algorithm for trivariate interpolation, which is based on the partition of unity method for constructing a global interpolant by blending local radial basis function interpolants and using locally supported weight functions. The partition of unity algorithm is efficiently implemented and optimized by connecting the method with an effective cube-partition searching procedure. More precisely, we construct a cube structure, which partitions the domain and strictly depends on the size of its subdomains, so that the new searching procedure and, accordingly, the resulting algorithm enable us to efficiently deal with a large number of nodes. Complexity analysis and numerical experiments show high efficiency and accuracy of the proposed interpolation algorithm.
MSC:
| 65D05 | Numerical interpolation |
| 65D15 | Algorithms for approximation of functions |
| 65D17 | Computer-aided design (modeling of curves and surfaces) |
Keywords:
meshless approximation; fast algorithms; partition of unity methods; radial basis functions; scattered dataReferences:
| [1] | G. Allasia, R. Besenghi, R. Cavoretto, and A. De Rossi, {\it Scattered and track data interpolation using an efficient strip searching procedure}, Appl. Math. Comput., 217 (2011), pp. 5949-5966. · Zbl 1213.65023 |
| [2] | I. Babuška and J. M. Melenk, {\it The partition of unity method}, Internat. J. Numer. Methods. Engrg., 40 (1997), pp. 727-758. · Zbl 0949.65117 |
| [3] | R. K. Beatson, W. A. Light, and S. Billings, {\it Fast solution of the radial basis function interpolation equations: Domain decomposition methods}, SIAM J. Sci. Comput., 22 (2000), pp. 1717-1740. · Zbl 0982.65015 |
| [4] | M. W. Berry and K. S. Minser, {\it Algorithm 798: High-dimensional interpolation using the modified Shepard method}, ACM Trans. Math. Software, 25 (1999), pp. 353-366. · Zbl 0963.65015 |
| [5] | M. Bozzini and M. Rossini, {\it Testing methods for 3D scattered data interpolation}, Monogr. Real Acad. Ci. Exact. Fis.-Quim. Nat. Zaragoza, 20 (2002), pp. 111-135. · Zbl 1036.65006 |
| [6] | M. D. Buhmann, {\it Radial Basis Functions: Theory and Implementation}, Cambridge Monogr. Appl. Comput. Math. 12, Cambridge University Press, Cambridge, UK, 2003. · Zbl 1038.41001 |
| [7] | R. Cavoretto and A. De Rossi, {\it Fast and accurate interpolation of large scattered data sets on the sphere}, J. Comput. Appl. Math., 234 (2010), pp. 1505-1521. · Zbl 1189.65024 |
| [8] | R. Cavoretto and A. De Rossi, {\it Spherical interpolation using the partition of unity method: An efficient and flexible algorithm}, Appl. Math. Lett., 25 (2012), pp. 1251-1256. · Zbl 1251.65008 |
| [9] | R. Cavoretto, A. De Rossi, M. Donatelli, and S. Serra-Capizzano, {\it Spectral analysis and preconditioning techniques for radial basis function collocation matrices}, Numer. Linear Algebra Appl., 19 (2012), pp. 31-52. · Zbl 1274.65308 |
| [10] | R. Cavoretto and A. De Rossi, {\it A meshless interpolation algorithm using a cell-based searching procedure}, Comput. Math. Appl., 67 (2014), pp. 1024-1038. · Zbl 1350.65012 |
| [11] | R. Cavoretto, {\it A numerical algorithm for multidimensional modeling of scattered data points}, Comput. Appl. Math., 34 (2015), pp. 65-80. · Zbl 1314.65021 |
| [12] | R. Cavoretto, G. E. Fasshauer, and M. McCourt, {\it An introduction to the Hilbert-Schmidt SVD using iterated Brownian bridge kernels}, Numer. Algorithms, 68 (2015), pp. 393-422. · Zbl 1309.65016 |
| [13] | R. Cavoretto and A. De Rossi, {\it A trivariate interpolation algorithm using a cube-partition searching procedure}, http://hdl.handle.net/2318/152999. · Zbl 1327.65022 |
| [14] | Y. Chen, S. Gottlied, A. Heryudono, and A. Narayan, {\it A reduced radial basis function method for partial differential equations on irregular domains}, J. Sci. Comput., to appear. · Zbl 1338.65252 |
| [15] | J. Cherrie, R. Beatson, and G. Newsam, {\it Fast evaluation of radial basis functions: Methods for generalized multiquadrics in \(\RR^n\)}, SIAM J. Sci. Comput., 23 (2002), pp. 1549-1571. · Zbl 1009.65007 |
| [16] | S. De Marchi and G. Santin, {\it A new stable basis for radial basis function interpolation}, J. Comput. Appl. Math., 253 (2013), pp. 1-13. · Zbl 1288.65013 |
| [17] | S. Deparis, D. Forti, and A. Quarteroni, {\it A rescaled localized radial basis function interpolation on non-Cartesian and nonconforming grids}, SIAM J. Sci. Comput., 36 (2014), pp. A2745-A2762. · Zbl 1312.41006 |
| [18] | G. E. Fasshauer, {\it Meshfree Approximation Methods with Matlab}, World Scientific Publishers, River Edge, NJ, 2007. · Zbl 1123.65001 |
| [19] | G. E. Fasshauer, {\it Positive definite kernels: Past, present and future}, Dolomites Res. Notes Approx., 4 (2011), pp. 21-63. |
| [20] | G. E. Fasshauer and M. J. McCourt, {\it Stable evaluation of Gaussian radial basis function interpolants}, SIAM J. Sci. Comput., 34 (2012), pp. A737-A762. · Zbl 1252.65028 |
| [21] | A. Iske, {\it Scattered data approximation by positive definite kernel functions}, Rend. Sem. Mat. Univ. Pol. Torino, 69 (2011), pp. 217-246. · Zbl 1263.65011 |
| [22] | M. A. Iyer, L. T. Watson, and M. W. Berry, {\it SHEPPACK: A Fortran 95 package for interpolation using the modified Shepard algorithm}, in Proceedings of the Annual Southeast Conference, R. Menezes et al., eds., ACM, New York, 2006, pp. 476-481. |
| [23] | D. Lazzaro and L. B. Montefusco, {\it Radial basis functions for the multivariate interpolation of large scattered data sets}, J. Comput. Appl. Math., 140 (2002), pp. 521-536. · Zbl 1025.65015 |
| [24] | J. M. Melenk and I. Babuška, {\it The partition of unity finite element method: Basic theory and applications}, Comput. Methods. Appl. Mech. Engrg., 139 (1996), pp. 289-314. · Zbl 0881.65099 |
| [25] | M. Pazouki and R. Schaback, {\it Bases for kernel-based spaces}, J. Comput. Appl. Math., 236 (2011), pp. 575-588. · Zbl 1234.41003 |
| [26] | R. J. Renka, {\it Multivariate interpolation of large sets of scattered data}, ACM Trans. Math. Software, 14 (1988), pp. 139-148. · Zbl 0642.65006 |
| [27] | R. J. Renka, {\it Algorithm 661: QSHEP \(3\) D: Quadratic Shepard method for trivariate interpolation of scattered data}, ACM Trans. Math. Software, 14 (1988), pp. 151-152. · Zbl 0709.65502 |
| [28] | A. Safdari-Vaighani, A. Heryudono, and E. Larsson, {\it A radial basis function partition of unity collocation method for convection-diffusion equations arising in financial applications}, J. Sci. Comput., 64 (2015), pp. 341-367. · Zbl 1325.65139 |
| [29] | R. Schaback, {\it Error estimates and condition numbers for radial basis function interpolation}, Adv. Comput. Math., 3 (1995), pp. 251-264. · Zbl 0861.65007 |
| [30] | W. I. Thacker, J. Zhang, L. T. Watson, J. B. Birch, M. A. Iyer, and M. W. Berry, {\it Algorithm 905: SHEPPACK: Modified Shepard algorithm for interpolation of scattered multivariate data}, ACM Trans. Math. Software, 37 (2010), pp. 1-20. · Zbl 1364.65028 |
| [31] | H. Wendland, {\it Fast evaluation of radial basis functions: Methods based on partition of unity}, in Approximation Theory X: Wavelets, Splines, and Applications, C. K. Chui, L. L. Schumaker, and J. St\ockler, eds., Vanderbilt University Press, Nashville, TN, 2002, pp. 473-483. · Zbl 1031.65022 |
| [32] | H. Wendland, {\it Scattered Data Approximation}, Cambridge Monogr. Appl. Comput. Math. 17, Cambridge University Press, Cambridge, UK, 2005. · Zbl 1075.65021 |
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.
