Top

Journal of Scientific Computing

Published in:

01-06-2015

Convexity and Solvability for Compactly Supported Radial Basis Functions with Different Shapes

Authors: Shengxin Zhu, Andrew J. Wathen

Published in: Journal of Scientific Computing | Issue 3/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is known that interpolation with radial basis functions of the same shape can guarantee a nonsingular interpolation matrix, whereas little was known when one uses various shapes. In this paper, we prove that functions from a class of compactly supported radial basis functions are convex on a certain region; based on this local convexity and other local geometrical properties of the interpolation points, we construct a sufficient condition which guarantees diagonally dominant interpolation matrices for radial basis functions interpolation with different shapes. The proof is constructive and can be used to design algorithms directly. Numerical examples show that the scheme has a low accuracy but can be implemented efficiently. It can be used for inaccurate models where efficiency is more desirable. Large scale 3D implicit surface reconstruction problems are used to demonstrate the utility and reasonable results can be obtained efficiently.

previous article Dynamic Model Adaptation for Multiscale Simulation of Hyperbolic Systems with Relaxation

next article Numerical Analysis of Penalty Stabilized Finite Element Discretizations of Evolution Navier–Stokes Equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://graphics.stanford.edu/data/3Dscanrep/.

http://www.cc.gatech.edu/projects/large_models/ply.html.

Bozzini, M., Lenarduzzi, L., Rossini, M., Schaback, R.: Interpolation by basis functions of different scales and shapes. Calcolo 41(2), 77–87 (2004). doi:10.1007/s10092-004-0085-6 CrossRefMATHMathSciNet

Bozzini, M., Lenarduzzi, L., Rossini, M., Schaback, R.: Interpolation with variably scaled kernels. IMA J. Numer. Anal. 1–21 (2014). doi:10.1093/imanum/drt071

Bozzini, M., Lenarduzzi, L., Schaback, R.: Adaptive interpolation by scaled multiquadrics. Adv. Comput. Math. 16(4), 375–387 (2002). doi:10.1023/A:1014584220418 CrossRefMATHMathSciNet

Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C., Evans, T.R.: Reconstruction and representation of 3d objects with radial basis functions. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pp. 67–76. ACM (2001)

Castrillón-Candás, J.E., Li, J., Eijkhout, V.: A discrete adapted hierarchical basis solver for radial basis function interpolation. BIT 53(1), 57–86 (2013). doi:10.1007/s10543-012-0397-x CrossRefMATHMathSciNet

Deng, Q., Driscoll, T.A.: A fast treecode for multiquadric interpolation with varying shape parameters. SIAM J. Sci. Comput. 34(2), A1126–A1140 (2012). doi:10.1137/110836225 CrossRefMATHMathSciNet

Dou, F.F., Hon, Y.C.: Kernel-based approximation for Cauchy problem of the time-fractional diffusion equation. Eng. Anal. Bound. Elem. 36(9), 1344–1352 (2012). doi:10.1016/j.enganabound.2012.03.003 CrossRefMathSciNet

Fasshauer, G.E.: Meshfree Approximation Methods with MATLAB, Interdisciplinary Mathematical Sciences, vol. 6. World Scientific Publishing Co., Pte. Ltd., Hackensack, NJ (2007). With 1 CD-ROM. Windows, Macintosh and UNIX

Flyer, N., Lehto, E.: Rotational transport on a sphere: local node refinement with radial basis functions. J. Comput. Phys. 229(6), 1954–1969 (2010). doi:10.1016/j.jcp.2009.11.016 CrossRefMATHMathSciNet

10.

Fornberg, B., Zuev, J.: The Runge phenomenon and spatially variable shape parameters in RBF interpolation. Comput. Math. Appl. 54(3), 379–398 (2007). doi:10.1016/j.camwa.2007.01.028 CrossRefMATHMathSciNet

11.

Fowkes, J.M., Gould, N.I.M., Farmer, C.L.: A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions. J. Global Optim. 56(4), 1791–1815 (2013). doi:10.1007/s10898-012-9937-9 CrossRefMATHMathSciNet

12.

Fuselier, E.J., Wright, G.B.: A high-order kernel method for diffusion and reaction-diffusion equations on surfaces. J. Sci. Comput. 56(3), 535–565 (2013). doi:10.1007/s10915-013-9688-x CrossRefMATHMathSciNet

13.

Holdahl, S.R., Hardy, R.L.: Solvability and multiquadric analysis as applied to investigations of vertical crustal movements. Tectonophysics 52(1–4), 139–155 (1979). doi:10.1016/0040-1951(79)90217-8. URL http://www.sciencedirect.com/science/article/pii/0040195179902178. Recent Crustal Movements

14.

Hon, Y.C., Wu, Z.: A quasi-interpolation method for solving stiff ordinary differential equations. Int. J. Numer. Methods Eng. 48(8), 1187–1197 (2000). doi:10.1002/(SICI)1097-0207(20000720)48:8<1187:AID-NME942>3.0.CO;2-K

15.

Jamshidi, A.A., Kirby, M.J.: Skew-radial basis function expansions for empirical modeling. SIAM J. Sci. Comput. 31(6), 4715–4743 (2009/10). doi:10.1137/08072293X

16.

Kansa, E.J.: Multiquadrics–a scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations. Comput. Math. Appl. 19(8–9), 147–161 (1990). doi:10.1016/0898-1221(90)90271-K CrossRefMATHMathSciNet

17.

Kansa, E.J., Carlson, R.E.: Improved accuracy of multiquadric interpolation using variable shape parameters. Comput. Math. Appl. 24(12), 99–120 (1992). doi:10.1016/0898-1221(92)90174-G. Advances in the theory and applications of radial basis functions

18.

Li, J.: Mixed methods for fourth-order elliptic and parabolic problems using radial basis functions. Adv. Comput. Math. 23(1–2), 21–30 (2005). doi:10.1007/s10444-004-1807-7 CrossRefMATHMathSciNet

19.

Li, M., Wang, Y., Ling, L.: Numerical caputo differentiation by radial basis functions. J. Sci. Comput. 1–16 (2014). doi:10.1007/s10915-014-9857-6

20.

Marchandise, E., Piret, C., Remacle, J.F.: CAD and mesh repair with radial basis functions. J. Comput. Phys. 231(5), 2376–2387 (2012). doi:10.1016/j.jcp.2011.11.033 CrossRefMATHMathSciNet

21.

Micchelli, C.A.: Interpolation of scattered data: distance matrices and conditionally positive definite functions. Constr. Approx. 2(1), 11–22 (1986). doi:10.1007/BF01893414 CrossRefMATHMathSciNet

22.

Sarra, S.A., Sturgill, D.: A random variable shape parameter strategy for radial basis function approximation methods. Eng. Anal. Bound. Elem. 33(11), 1239–1245 (2009). doi:10.1016/j.enganabound.2009.07.003 CrossRefMATHMathSciNet

23.

Shankar, V., Wright, G.B., Fogelson, A.L., Kirby, R.M.: A radial basis function finite difference method for the simulation of reaction-diffusion equations on stationary platelets within the augmented forcing method. Int. J. Numer. Meth. Fl. 75(1), 1–22 (2014). doi:10.1002/fld.3880

24.

Strang, G., Fix, G.: A fourier analysis of the finite element variational method. In: Constructive Aspects of Functional Analysis. Springer, New York, pp. 793–840 (1971)

25.

Varga, R.S.: Matrix Iterative Analysis, Springer Series in Computational Mathematics, vol. 27, expanded edn. Springer, Berlin (2000). doi:10.1007/978-3-642-05156-2

26.

Varga, R.S., Saff, E.B., Mehrmann, V.: Incomplete factorizations of matrices and connections with\(H\)-matrices. SIAM J. Numer. Anal. 17(6), 787–793 (1980). doi: 10.1137/0717066 CrossRefMATHMathSciNet

27.

Wei, T., Hon, Y.C., Wang, Y.B.: Reconstruction of numerical derivatives from scattered noisy data. Inverse Probl. 21(2), 657–672 (2005). doi:10.1088/0266-5611/21/2/013 CrossRefMATHMathSciNet

28.

Wendland, H.: Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17. Cambridge University Press, Cambridge (2005)

29.

Wu, Z.: Compactly supported radial functions and the Strang-Fix condition. Appl. Math. Comput. 84(2–3), 115–124 (1997). doi:10.1016/S0096-3003(96)00110-5 CrossRefMATHMathSciNet

30.

Wu, Z.M.: Compactly supported positive definite radial functions. Adv. Comput. Math. 4(3), 283–292 (1995). doi:10.1007/BF03177517 CrossRefMATHMathSciNet

31.

Wu, Z.M., Liu, J.P.: Generalized Strang-Fix condition for scattered data quasi-interpolation. Adv. Comput. Math. 23(1–2), 201–214 (2005). doi:10.1007/s10444-004-1832-6 CrossRefMATHMathSciNet

32.

Zhou, F., Zhang, J., Sheng, X., Li, G.: Shape variable radial basis function and its application in dual reciprocity boundary face method. Eng. Anal. Bound. Elem. 35(2), 244–252 (2011). doi:10.1016/j.enganabound.2010.08.009 CrossRefMATHMathSciNet

33.

Zhu, S., Wathen, A.J.: Fast Sparse Kernel Summation on Cartesian Grids. Tech. Rep. 1820, The University of Oxford, Oxford (2014). URL http://eprints.maths.ox.ac.uk/1820/

Title: Convexity and Solvability for Compactly Supported Radial Basis Functions with Different Shapes
Authors: Shengxin Zhu
Andrew J. Wathen
Publication date: 01-06-2015
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 3/2015
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-014-9919-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2015

Local Discontinuous Galerkin Methods for the Functionalized Cahn–Hilliard Equation

Pressure Recovery for Weakly Over-Penalized Discontinuous Galerkin Methods for the Stokes Problem

Contraction and Optimality Properties of an Adaptive Legendre–Galerkin Method: The Multi-Dimensional Case

Well-Balanced Central Schemes on Overlapping Cells with Constant Subtraction Techniques for the Saint-Venant Shallow Water System

Numerical Analysis of Penalty Stabilized Finite Element Discretizations of Evolution Navier–Stokes Equations

Error Analysis of Explicit Partitioned Runge–Kutta Schemes for Conservation Laws

Premium Partner