Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T12:48:06.480Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving PDEs with radial basis functions*

Published online by Cambridge University Press:  27 April 2015

Bengt Fornberg  and
Natasha Flyer
Bengt Fornberg
Affiliation:
Department of Applied Mathematics, University of Colorado, Boulder, CO 80309, USA E-mail: [email protected]
Natasha Flyer
Affiliation:
Institute for Mathematics Applied to Geosciences, National Center for Atmospheric Research, Boulder, CO 80305, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Finite differences provided the first numerical approach that permitted large-scale simulations in many applications areas, such as geophysical fluid dynamics. As accuracy and integration time requirements gradually increased, the focus shifted from finite differences to a variety of different spectral methods. During the last few years, radial basis functions, in particular in their ‘local’ RBF-FD form, have taken the major step from being mostly a curiosity approach for small-scale PDE ‘toy problems’ to becoming a major contender also for very large simulations on advanced distributed memory computer systems. Being entirely mesh-free, RBF-FD discretizations are also particularly easy to implement, even when local refinements are needed. This article gives some background to this development, and highlights some recent results.

Type
Research Article
Information
Acta Numerica , Volume 24 , 01 May 2015 , pp. 215 - 258
Copyright
© Cambridge University Press, 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barnett, G. A., Flyer, N. and Wicker, L. J. (2015), An RBF-FD polynomial method for nonhydrostatic atmospheric modeling on different node layouts. Submitted.Google Scholar
Bayona, V. and Kindelan, M. (2013), ‘Propagation of premixed laminar flames in 3D narrow open ducts using RBF-generated finite differences’, Combust. Theory Model. 17, 789–803.CrossRefGoogle Scholar
Bercovici, D., Schubert, G., Glatzmaier, G. A. and Zebib, A. (1989), ‘Three-dimensional thermal convection in a spherical shell’, J. Fluid Mech. 206, 75–104.CrossRefGoogle Scholar
Blaise, S. and St-Cyr, A. (2012), ‘A dynamic $hp$ -adaptive discontinuous Galerkin method for shallow water flows on the sphere with application to a global tsunami simulation’, Mon. Weather Rev. 140, 978–996.CrossRefGoogle Scholar
Bochner, S. (1933), ‘Monotone Functionen, Stieltjes Integrale und harmonische Analyse’, Math. Ann. 108, 378–410.CrossRefGoogle Scholar
Bollig, E., Flyer, N. and Erlebacher, G. (2012), ‘Solution to PDEs using radial basis function finite-differences (RBF-FD) on multiple GPUs’, J. Comput. Phys. 231, 7133–7151.CrossRefGoogle Scholar
Boyd, J. P. (2000), Chebyshev and Fourier Spectral Methods, Dover.Google Scholar
Buhmann, M. D. (2000), Radial basis functions. In Acta Numerica, Vol. 9, Cambridge University Press, pp. 1–38.Google Scholar
Buhmann, M. D. (2003), Radial Basis Functions: Theory and Implementations, Vol. 12 of Cambridge Monographs on Applied and Computational Mathematics , Cambridge University Press.CrossRefGoogle Scholar
Chen, W., Fu, Z.-J. and Chen, C. S. (2014), Recent Advances in Radial Basis Function Collocation Methods, Springer Briefs in Applied Sciences and Technology, Springer.CrossRefGoogle Scholar
Chinchapatnam, P. P., Djidjeli, K., Nair, P. B. and Tan, M. (2009), ‘A compact RBF-FD based meshless method for the incompressible Navier–Stokes equations’, J. Eng. Maritime Env. 223, 275–290.Google Scholar
Collatz, L. (1960), The Numerical Treatment of Differential Equations, Springer.Google Scholar
Curtis, P. C. J. (1959), ‘ $n$ -parameter families and best approximation’, Pacific J. Math. 93, 1013–1027.CrossRefGoogle Scholar
Driscoll, T. A. and Fornberg, B. (2002), ‘Interpolation in the limit of increasingly flat radial basis functions’, Comput. Math. Appl. 43, 413–422.CrossRefGoogle Scholar
Duchon, J. (1977), Splines minimizing rotation-invariant semi-norms in Sobolev spaces. In Constructive Theory of Functions of Several Variables, Vol. 571 of Lecture Notes in Mathematics (Schempp, W. and Zeller, K., eds), Springer, pp. 85–100.CrossRefGoogle Scholar
Fasshauer, G. E. (1997), Solving partial differential equations by collocation with radial basis functions. In Surface Fitting and Multiresolution Method, Vol. 2, Proc. 3rd International Conference on Curves and Surfaces (Le Méhauté, A., Rabut, C. and Schumaker, L. L., eds), Vanderbilt University Press, pp. 131–138.Google Scholar
Fasshauer, G. E. (2007), Meshfree Approximation Methods with MATLAB, Vol. 6, Interdisciplinary Mathematical Sciences , World Scientific.CrossRefGoogle Scholar
Flyer, N. and Fornberg, B. (2011), ‘Radial basis functions: Developments and applications to planetary scale flows’, Comput. and Fluids 46, 23–32.CrossRefGoogle Scholar
Flyer, N. and Lehto, E. (2010), ‘Rotational transport on a sphere: Local node refinement with radial basis functions’, J. Comput. Phys. 229, 1954–1969.CrossRefGoogle Scholar
Flyer, N. and Wright, G. B. (2007), ‘Transport schemes on a sphere using radial basis functions’, J. Comput. Phys. 226, 1059–1084.CrossRefGoogle Scholar
Flyer, N. and Wright, G. B. (2009), ‘A radial basis function method for the shallow water equations on a sphere’, Proc. Roy. Soc. A 465, 1949–1976.CrossRefGoogle Scholar
Flyer, N., Lehto, E., Blaise, S., Wright, G. B. and St-Cyr, A. (2012), ‘A guide to RBF-generated finite differences for nonlinear transport: Shallow water simulations on a sphere’, J. Comput. Phys. 231, 4078–4095.CrossRefGoogle Scholar
Fornberg, B. (1987), ‘The pseudospectral method: Comparisons with finite differences for the elastic wave equation’, Geophysics 52, 483–501.CrossRefGoogle Scholar
Fornberg, B. (1996), A Practical Guide to Pseudospectral Methods, Cambridge University Press.CrossRefGoogle Scholar
Fornberg, B. (1998), ‘Calculations of weights in finite difference formulas’, SIAM Rev. 40, 685–691.CrossRefGoogle Scholar
Fornberg, B. and Flyer, N. (2015a), ‘Fast generation of 2-D node distributions for mesh-free PDE discretizations’, Comput. Math. Appl. doi:10.1016/j.camwa.2015.01.009 CrossRefGoogle Scholar
Fornberg, B. and Flyer, N. (2015b), A Primer on Radial Basis Functions with Applications to the Geosciences, SIAM.CrossRefGoogle Scholar
Fornberg, B. and Lehto, E. (2011), ‘Stabilization of RBF-generated finite difference methods for convective PDEs’, J. Comput. Phys. 230, 2270–2285.CrossRefGoogle Scholar
Fornberg, B. and Piret, C. (2007), ‘A stable algorithm for flat radial basis functions on a sphere’, SIAM J. Sci. Comput. 30, 60–80.CrossRefGoogle Scholar
Fornberg, B. and Piret, C. (2008), ‘On choosing a radial basis function and a shape parameter when solving a convective PDE on a sphere’, J. Comput. Phys. 227, 2758–2780.CrossRefGoogle Scholar
Fornberg, B. and Wright, G. (2004), ‘Stable computation of multiquadric interpolants for all values of the shape parameter’, Comput. Math. Appl. 48, 853–867.CrossRefGoogle Scholar
Fornberg, B. and Zuev, J. (2007), ‘The Runge phenomenon and spatially variable shape parameters in RBF interpolation’, Comput. Math. Appl. 54, 379–398.CrossRefGoogle Scholar
Fornberg, B., Driscoll, T. A., Wright, G. and Charles, R. (2002), ‘Observations on the behavior of radial basis functions near boundaries’, Comput. Math. Appl. 43, 473–490.CrossRefGoogle Scholar
Fornberg, B., Larsson, E. and Flyer, N. (2011), ‘Stable computations with Gaussian radial basis functions’, SIAM J. Sci. Comput. 33, 869–892.CrossRefGoogle Scholar
Fornberg, B., Larsson, E. and Wright, G. B. (2006), ‘A new class of oscillatory radial basis functions’, Comput. Math. Appl. 51, 1209–1222.CrossRefGoogle Scholar
Fornberg, B., Lehto, E. and Powell, C. (2013), ‘Stable calculation of Gaussian-based RBF-FD stencils’, Comput. Math. Appl. 65, 627–637.CrossRefGoogle Scholar
Fornberg, B., Wright, G. and Larsson, E. (2004), ‘Some observations regarding interpolants in the limit of flat radial basis functions’, Comput. Math. Appl. 47, 37–55.CrossRefGoogle Scholar
Fox, L. (1947), ‘Some improvements in the use of relaxation methods for the solution of ordinary and partial differential equations’, Proc. Roy. Soc. A 190, 31–59.Google Scholar
Fuselier, E. J. and Wright, G. B. (2013), ‘A high-order kernel method for diffusion and reaction–diffusion equations on surfaces’, J. Sci. Comput. 56, 535–565.CrossRefGoogle Scholar
Giraldo, F. X. and Restelli, M. (2008), ‘A study of spectral element and discontinuous Galerkin methods for the Navier–Stokes equations in nonhydrostatic mesoscale atmospheric modeling: Equation sets and test cases’, J. Comput. Phys. 227, 3849–3877.CrossRefGoogle Scholar
Gupta, M. M. (1991), ‘High accuracy solutions of incompressible Navier–Stokes equations’, J. Comput. Phys. 93, 343–359.CrossRefGoogle Scholar
Harder, H. and Hansen, U. (2005), ‘A finite-volume solution method for thermal convection and dynamo problems in spherical shells’, Geophys. J. Int. 161, 522–532.CrossRefGoogle Scholar
Hardy, R. L. (1971), ‘Multiquadric equations of topography and other irregular surfaces’, J. Geophys. Res. 76, 1905–1915.CrossRefGoogle Scholar
Hon, Y. C. and Schaback, R. (2001), ‘On unsymmetric collocation by radial basis functions’, Appl. Math. Comput. 119, 177–186.Google Scholar
Iske, A. (2004), Multiresolution Methods in Scattered Data Modelling, Vol. 37 of Lecture Notes in Computational Science and Engineering , Springer.CrossRefGoogle Scholar
Kameyama, M. C., Kageyama, A. and Sato, T. (2008), ‘Multigrid-based simulation code for mantle convection in spherical shell using Yin–Yang grid’, Phys. Earth Planet. Interiors 171, 19–32.CrossRefGoogle Scholar
Kansa, E. J. (1990a), ‘Multiquadrics: A scattered data approximation scheme with applications to computational fluid-dynamics, part I: Surface approximations and parital derivative estimates’, Comput. Math. Appl. 19, 127–145.CrossRefGoogle Scholar
Kansa, E. J. (1990b), ‘Multiquadrics: A scattered data approximation scheme with applications to computational fluid-dynamics, part II: Solutions to parabolic, hyperbolic and elliptic partial differential equations’, Comput. Math. Appl. 19, 147–161.CrossRefGoogle Scholar
Kee, B. B. T., Liu, G. R. and Lu, C. (2008), ‘A least-square radial point collocation method for adaptive analysis in linear elasticity’, Eng. Anal. Bound. Elem. 32, 440–460.CrossRefGoogle Scholar
Kindelan, M., Bernal, F., Gonzalez-Rodriguez, P. and Moscoso, M. (2010), ‘Application of the RBF meshless method to the solution of the radiative transport equation’, J. Comput. Phys. 229, 1897–1908.CrossRefGoogle Scholar
Larsson, E. and Fornberg, B. (2003), ‘A numerical study of some radial basis function based solution methods for elliptic PDEs’, Comput. Math. Appl. 46, 891–902.CrossRefGoogle Scholar
Larsson, E., Lehto, E., Heryudono, A. and Fornberg, B. (2013), ‘Stable computation of differentiation matrices and scattered node stencils based on Gaussian radial basis functions’, SIAM J. Sci. Comput. 35, A2096–A2119.CrossRefGoogle Scholar
Lele, S. K. (1992), ‘Compact finite difference schemes with spectral-like resolution’, J. Comput. Phys. 103, 16–42.CrossRefGoogle Scholar
Li, M., Tang, T. and Fornberg, B. (1995), ‘A compact fourth-order finite difference scheme for the steady incompressible Navier–Stokes equations’, Internat. J. Numer. Meth. Fluids 20, 1137–1151.CrossRefGoogle Scholar
Lombard, B. and Piraux, J. (2004), ‘Numerical treatment of two-dimensional interfaces for acoustic and elastic waves’, J. Comput. Phys. 195, 90–116.CrossRefGoogle Scholar
Lombard, B., Piraux, J., Gelis, C. and Virieux, J. (2008), ‘Free and smooth boundaries in 2-D finite-difference schemes for transient elastic waves’, Geophys. J. Int. 172, 252–261.CrossRefGoogle Scholar
Madych, W. R. and Nelson, S. A. (1992), ‘Bounds on multivariate polynomials and exponential error estimates for multiquadric interpolation’, J. Approx. Theory 70, 94–114.CrossRefGoogle Scholar
Mairhuber, J. C. (1956), ‘On Haar’s theorem concerning Chebyshev approximation problems having unique solutions’, Proc. Amer. Math. Soc 7, 609–615.Google Scholar
Martin, B., Fornberg, B. and St-Cyr, A. (2015), ‘Seismic modeling with radial basis function-generated finite differences (RBF-FD)’, Geophysics, to appear.CrossRefGoogle Scholar
Martin, G. S., Wiley, R. and Marfurt, K. J. (2006), ‘Marmousi2: An elastic upgrade for Marmousi’, The Leading Edge 25, 156–166.CrossRefGoogle Scholar
Micchelli, C. A. (1986), ‘Interpolation of scattered data: Distance matrices and conditionally positive definite functions’, Constr. Approx. 2, 11–22.CrossRefGoogle Scholar
Norman, M. R., Nair, R. D. and Semazzi, F. H. M. (2011), ‘A low communication and large time step explicit finite-volume solver for non-hydrostatic atmospheric dynamics’, J. Comput. Phys. 230, 1567–1584.CrossRefGoogle Scholar
Persson, P.-O. and Strang, G. (2004), ‘A simple mesh generator in MATLAB’, SIAM Rev. 46, 329–345.CrossRefGoogle Scholar
Piret, C. (2012), ‘The orthogonal gradients method: A radial basis functions method for solving partial differential equations on arbitrary surfaces’, J. Comput. Phys. 231, 4662–4675.CrossRefGoogle Scholar
Powell, M. J. D. (1992), The theory of radial basis function approximation in 1990. In Advances in Numerical Analysis, Vol. II, Wavelets, Subdivision Algorithms and Radial Functions (Light, W., ed.), Oxford University Press, pp. 105–210.CrossRefGoogle Scholar
Powell, M. J. D. (2005), Five lectures on radial basis functions. Technical report, Technical University of Denmark, Lyngby.Google Scholar
Power, H. and Barraco, V. (2002), ‘A comparison analysis between unsymmetric and symmetric radial basis function collocation methods for the numerical solution of partial differential equations’, Comput. Math. Appl. 43, 551–583.CrossRefGoogle Scholar
Richardson, L. F. (1911), ‘The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam’, Phil. Trans. Royal Soc. London 210, 307–357.Google Scholar
Rodrigues, J. D., Roque, C. M. C. and Ferreira, A. J. M. (2013), ‘An improved meshless method for the static and vibration analysis of plates’, Mechanics Based Design of Structures and Machines 41, 21–39.CrossRefGoogle Scholar
Schaback, R. (1995), ‘Error estimates and condition numbers for radial basis function interpolants’, Adv. Comput. Math. 3, 251–264.CrossRefGoogle Scholar
Schaback, R. (2005), ‘Multivariate interpolation by polynomials and radial basis functions’, Constr. Approx. 21, 293–317.CrossRefGoogle Scholar
Schaback, R. and Wendland, H. (2006), Kernel techniques: From machine learning to meshless methods. In Acta Numerica, Vol. 15, Cambridge University Press, pp. 543–639.Google Scholar
Schoenberg, I. J. (1938), ‘Metric spaces and completely monotone functions’, Ann. of Math. 39, 811–841.CrossRefGoogle Scholar
Shankar, V., Wright, G. B., Fogelson, A. L. and Kirby, R. M. (2013), ‘A study of different modeling choices for simulating platelets within the immersed boundary method’, Appl. Numer. Math. 63, 58–77.CrossRefGoogle ScholarPubMed
Shu, C., Ding, H. and Yeo, K. S. (2003), ‘Local radial basis function-based differential quadrature method and its application to solve two-dimensional incompressible Navier–Stokes equations’, Comput. Methods Appl. Mech. Engrg 192, 941–954.CrossRefGoogle Scholar
Skamarock, W. C. and Klemp, J. B. (2008), ‘A time-split nonhydrostatic atmospheric model for weather research and forecasting applications’, J. Comput. Phys. 227, 3465–3485.CrossRefGoogle Scholar
Stemmer, K., Harder, H. and Hansen, U. (2006), ‘A new method to simulate convection with strongly temperature- and pressure-dependent viscosity in a spherical shell: Applications to the Earth’s mantle’, Phys. Earth Planet. Inter. 157, 223–249.CrossRefGoogle Scholar
Straka, J., Wilhelmson, R., Wicker, L., Anderson, J. and Droegemeier, K. (1993), ‘Numerical solutions of a nonlinear density current: A benchmark solution and comparisons’, Internat. J. Numer. Meth. Fluids 17, 1–22.CrossRefGoogle Scholar
Symes, W. W. and Vdovina, T. (2009), ‘Interface error analysis for numerical wave propagation’, Comput. Geosci. 13, 363–370.CrossRefGoogle Scholar
Takacs, L. (1988), ‘Effects of using a posteriori methods for the conservation of integral invariants’, Mon. Weather Rev. 116, 525–545.2.0.CO;2>CrossRefGoogle Scholar
Tarwater, A. E. (1985), Parameter study of Hardy’s multiquadric method for scattered data interpolation. Technical report UCRL-54670, Lawrence Livermore National Laboratory.Google Scholar
Tolstykh, A. I. (2000), ‘On using RBF-based differencing formulas for unstructured and mixed structured–unstructured grid calculations’, Proc. 16th IMACS World Congress 228, 4606–4624.Google Scholar
Tolstykh, A. I. and Shirobokov, D. A. (2003), ‘On using radial basis functions in a “finite difference mode” with applications to elasticity problems’, Comput. Mech. 33, 68–79.CrossRefGoogle Scholar
Trefethen, L. N. (2000), Spectral Methods in MATLAB, SIAM.CrossRefGoogle Scholar
Turing, A. M. (1952), ‘The chemical basis of morphogenesis’, Phil. Trans Royal Soc. London B 237, 37–72.Google Scholar
Wang, J. G. and Liu, G. R. (2002), ‘A point interpolation meshless method based on radial basis functions’, Internat. J. Numer. Meth. Engrg 54, 1623–1648.CrossRefGoogle Scholar
Wendland, H. (2005), Scattered Data Approximation. Vo. 17 of Cambridge Monographs on Applied and Computational Mathematics , Cambridge University Press.Google Scholar
Williamson, D. L., Drake, J. B., Hack, J. J., Jakob, R. and Swarztrauber, P. N. (1992), ‘A standard test set for numerical approximations to the shallow water equations in spherical geometry’, J. Comput. Phys. 102, 211–224.CrossRefGoogle Scholar
Wright, G. B. (2003), Radial basis function interpolation: Numerical and analytical developments. PhD thesis, University of Colorado.Google Scholar
Wright, G. B. and Fornberg, B. (2006), ‘Scattered node compact finite difference-type formulas generated from radial basis functions’, J. Comput. Phys. 212, 99–123.CrossRefGoogle Scholar
Wright, G. B., Flyer, N. and Yuen, D. A. (2010), ‘A hybrid radial basis function: Pseudospectral method for thermal convection in a 3D spherical shell’, Geochem. Geophys. Geosyst. 11, Q07003.CrossRefGoogle Scholar
Wu, Z. (1992), ‘Hermite–Birkhoff interpolation of scattered data by radial basis functions’, Approx. Theory Appl. 8, 1–10.Google Scholar
Yu, Y. and Chen, Z. (2011), ‘Implementation of material interface conditions in the radial point interpolation methless method’, IEEE Trans. Ant. Prop. 59, 2916–2923.CrossRefGoogle Scholar
Zhai, S., Feng, X. and He, Y. (2013), ‘A family of fourth-order and sixth-order compact difference schemes for the three-dimensional Poisson equation’, J. Sci. Comput. 54, 97–120.CrossRefGoogle Scholar
Zhong, S., McNamara, A., Tan, E., Moresi, L. and Gurnis, M. (2008), ‘A benchmark study on mantle convection in a 3-D spherical shell using CitcomS’, Geochem. Geophys. Geosyst. 9, Q10017.CrossRefGoogle Scholar