Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scientific Computing
Published in: Journal of Scientific Computing 3/2023

01-09-2023

Monotone Meshfree Methods for Linear Elliptic Equations in Non-divergence Form via Nonlocal Relaxation

Authors: Qihao Ye, Xiaochuan Tian

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

Log in

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

search-config
loading …

Abstract

We design a monotone meshfree finite difference method for linear elliptic equations in the non-divergence form on point clouds via a nonlocal relaxation method. The key idea is a novel combination of a nonlocal integral relaxation of the PDE problem with a robust meshfree discretization on point clouds. Minimal positive stencils are obtained through a local \(l_1\)-type optimization procedure that automatically guarantees the stability and, therefore, the convergence of the meshfree discretization for linear elliptic equations. A major theoretical contribution is the existence of consistent and positive stencils for a given point cloud geometry. We provide sufficient conditions for the existence of positive stencils by finding neighbors within an ellipse (2d) or ellipsoid (3d) surrounding each interior point, generalizing the study for Poisson’s equation by Seibold (Comput Methods Appl Mech Eng 198(3–4):592–601, 2008). It is well-known that wide stencils are in general needed for constructing consistent and monotone finite difference schemes for linear elliptic equations. Our result represents a significant improvement in the stencil width estimate for positive-type finite difference methods for linear elliptic equations in the near-degenerate regime (when the ellipticity constant becomes small), compared to previously known works in this area. Numerical algorithms and practical guidance are provided with an eye on the case of small ellipticity constant. At the end, we present numerical results for the performance of our method in both 2d and 3d, examining a range of ellipticity constants including the near-degenerate regime.
previous article A Physical-Constraint-Preserving Discontinuous Galerkin Method for Weakly Compressible Two-Phase Flows
next article Conjugate Gradients Acceleration of Coordinate Descent for Linear Systems

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
Appendix
Available only for authorised users
Literature
1.
Abdulle, A., Weinan, E.: Finite difference heterogeneous multi-scale method for homogenization problems. J. Comput. Phys. 191(1), 18–39 (2003)MathSciNetMATHCrossRef
2.
Aksoylu, B., Gazonas, G.A.: On the choice of kernel function in nonlocal wave propagation. J. Peridyn. Nonlocal Model. 2(4), 379–400 (2020)MathSciNetCrossRef
3.
Andreu-Vaillo, F., Mazón, J.M., Rossi, J.D., Toledo-Melero, J.J.: Nonlocal Diffusion Problems, vol. 165. American Mathematical Society, Providence (2010)
4.
Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991)MathSciNetMATH
5.
Beale, J.T., Majda, A.: Vortex methods. I. Convergence in three dimensions. Math. Comput. 39(159), 1–27 (1982)MathSciNetMATH
6.
Belytschko, T., Guo, Y., Kam Liu, W., Ping Xiao, S.: A unified stability analysis of meshless particle methods. Int. J. Numer. Methods Eng. 48(9), 1359–1400 (2000)MathSciNetMATHCrossRef
7.
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)MATHCrossRef
8.
Bucur, C., Valdinoci, E.: Nonlocal Diffusion and Applications, vol. 20. Springer, New York (2016)MATH
9.
Buhmann, M.D.: Radial Basis Functions: Theory and Implementations, vol. 12. Cambridge University Press, Cambridge (2003)MATHCrossRef
10.
Cabré, X.: Elliptic pde’s in probability and geometry: symmetry and regularity of solutions. Discrete Contin. Dyn. Syst. 20(3), 425 (2008)MathSciNetMATHCrossRef
11.
Caffarelli, L.A., Gutiérrez, C.E.: Properties of the solutions of the linearized Monge–Ampere equation. Am. J. Math. 119(2), 423–465 (1997)MathSciNetMATHCrossRef
12.
Cottet, G.H., Koumoutsakos, P.D., et al.: Vortex Methods: Theory and Practice, vol. 8. Cambridge University Press Cambridge, Cambridge (2000)MATHCrossRef
13.
14.
Crandall, M.G., Ishii, H., Lions, P.L.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. 27(1), 1–67 (1992)MathSciNetMATHCrossRef
15.
Dantzig, G.B.: Origins of the simplex method. In: A History of Scientific Computing, pp. 141–151 (1990)
16.
17.
D’Elia, M., Du, Q., Glusa, C., Gunzburger, M., Tian, X., Zhou, Z.: Numerical methods for nonlocal and fractional models. Acta Numer. 29, 1–124 (2020)MathSciNetMATHCrossRef
18.
Demkowicz, L., Karafiat, A., Liszka, T.: On some convergence results for FDM with irregular mesh. Comput. Methods Appl. Mech. Eng. 42(3), 343–355 (1984)MathSciNetMATHCrossRef
19.
20.
Du, Q., Gunzburger, M., Lehoucq, R.B., Zhou, K.: Analysis and approximation of nonlocal diffusion problems with volume constraints. SIAM Rev. 54(4), 667–696 (2012)MathSciNetMATHCrossRef
21.
Du, Q., Lehoucq, R.B., Tartakovsky, A.M.: Integral approximations to classical diffusion and smoothed particle hydrodynamics. Comput. Methods Appl. Mech. Eng. 286, 216–229 (2015)MathSciNetMATHCrossRef
22.
Fan, Y., You, H., Tian, X., Yang, X., Li, X., Prakash, N., Yu, Y.: A meshfree peridynamic model for brittle fracture in randomly heterogeneous materials. Comput. Methods Appl. Mech. Eng. 339, 115340 (2022)MathSciNetMATHCrossRef
23.
Feng, X., Glowinski, R., Neilan, M.: Recent developments in numerical methods for fully nonlinear second order partial differential equations. SIAM Rev. 55(2), 205–267 (2013)MathSciNetMATHCrossRef
24.
Feng, X., Hennings, L., Neilan, M.: Finite element methods for second order linear elliptic partial differential equations in non-divergence form. Math. Comput. 86(307), 2025–2051 (2017)MathSciNetMATHCrossRef
25.
Feng, X., Lewis, T.: A narrow-stencil finite difference method for approximating viscosity solutions of Hamilton–Jacobi–Bellman equations. SIAM J. Numer. Anal. 59(2), 886–924 (2021)MathSciNetMATHCrossRef
26.
Feng, X., Neilan, M., Schnake, S.: Interior penalty discontinuous Galerkin methods for second order linear non-divergence form elliptic pdes. J. Sci. Comput. 74(3), 1651–1676 (2018)MathSciNetMATHCrossRef
27.
Finlay, C., Oberman, A.: Improved accuracy of monotone finite difference schemes on point clouds and regular grids. SIAM J. Sci. Comput. 41(5), A3097–A3117 (2019)MathSciNetMATHCrossRef
28.
Fleming, W.H., Soner, H.M.: Controlled Markov Processes and Viscosity Solutions, vol. 25. Springer, New York (2006)MATH
29.
Froese, B.D.: Meshfree finite difference approximations for functions of the eigenvalues of the Hessian. Numer. Math. 138(1), 75–99 (2018)MathSciNetMATHCrossRef
30.
Froese, B.D., Oberman, A.M.: Convergent finite difference solvers for viscosity solutions of the elliptic Monge–Ampère equation in dimensions two and higher. SIAM J. Numer. Anal. 49(4), 1692–1714 (2011)MathSciNetMATHCrossRef
31.
32.
García Trillos, N., Gerlach, M., Hein, M., Slepčev, D.: Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator. Found. Comput. Math. 20(4), 827–887 (2020)MathSciNetMATHCrossRef
33.
Gilbarg, D., Trudinger, N.S.: Elliptic Partial Differential Equations of Second Order, vol. 224. Springer, Berlin (1977)MATH
34.
Gingold, R.A., Monaghan, J.J.: Smoothed particle hydrodynamics: theory and application to non-spherical stars. Mon. Not. R. Astron. Soc. 181(3), 375–389 (1977)MATHCrossRef
35.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57 (1984)
36.
Hamfeldt, B.F., Lesniewski, J.: Convergent finite difference methods for fully nonlinear elliptic equations in three dimensions. J. Sci. Comput. 90(1), 1–36 (2022)MathSciNetMATHCrossRef
37.
Kocan, M.: Approximation of viscosity solutions of elliptic partial differential equations on minimal grids. Numer. Math. 72(1), 73–92 (1995)MathSciNetMATHCrossRef
38.
Kuo, H.J., Trudinger, N.S.: Linear elliptic difference inequalities with random coefficients. Math. Comput. 55(191), 37–53 (1990)MathSciNetMATHCrossRef
39.
Lakkis, O., Pryer, T.: A finite element method for second order nonvariational elliptic problems. SIAM J. Sci. Comput. 33(2), 786–801 (2011)MathSciNetMATHCrossRef
40.
41.
Le, N.Q., Mitake, H., Tran, H.V.: Dynamical and Geometric Aspects of Hamilton–Jacobi and Linearized Monge–Ampère Equations. Springer, New York (2017)MATHCrossRef
42.
Leng, Y., Tian, X., Trask, N., Foster, J.T.: Asymptotically compatible reproducing kernel collocation and meshfree integration for nonlocal diffusion. SIAM J. Numer. Anal. 59(1), 88–118 (2021)MathSciNetMATHCrossRef
43.
Li, Z., Shi, Z.: A convergent point integral method for isotropic elliptic equations on a point cloud. Multiscale Model. Simul. 14(2), 874–905 (2016)MathSciNetMATHCrossRef
44.
Liszka, T., Duarte, C., Tworzydlo, W.: Hp-meshless cloud method. Comput. Methods Appl. Mech. Eng. 139(1–4), 263–288 (1996)MATHCrossRef
45.
Liu, M.B., Liu, G.R.: Smoothed particle hydrodynamics (SPH): an overview and recent developments. Arch. Comput. Methods Eng. 17, 25–76 (2010)MathSciNetMATHCrossRef
46.
Liu, W.K., Chen, Y., Jun, S., Chen, J., Belytschko, T., Pan, C., Uras, R., Chang, C.: Overview and applications of the reproducing kernel particle methods. Arch. Comput. Methods Eng. 3(1), 3–80 (1996)MathSciNetCrossRef
47.
Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998)MATHCrossRef
48.
Maugeri, A., Palagachev, D.K., Softova, L.: Elliptic and parabolic equations with discontinuous coefficients. Math. Res. 6, 66 (2000)MATH
49.
Mirebeau, J.M.: Minimal stencils for discretizations of anisotropic pdes preserving causality or the maximum principle. SIAM J. Numer. Anal. 54(3), 1582–1611 (2016)MathSciNetMATHCrossRef
50.
Mirzaei, D., Schaback, R., Dehghan, M.: On generalized moving least squares and diffuse derivatives. IMA J. Numer. Anal. 32(3), 983–1000 (2012)MathSciNetMATHCrossRef
51.
Motzkin, T.S., Wasow, W.: On the approximation of linear elliptic differential equations by difference equations with positive coefficients. J. Math. Phys. 31(1–4), 253–259 (1952)MathSciNetMATHCrossRef
52.
53.
54.
Nochetto, R., Ntogkas, D., Zhang, W.: Two-scale method for the Monge–Ampère equation: convergence to the viscosity solution. Math. Comput. 88(316), 637–664 (2019)MATHCrossRef
55.
Nochetto, R.H., Zhang, W.: Discrete ABP estimate and convergence rates for linear elliptic equations in non-divergence form. Found. Comput. Math. 18(3), 537–593 (2018)MathSciNetMATHCrossRef
56.
Nochetto, R.H., Zhang, W.: Pointwise rates of convergence for the Oliker–Prussner method for the Monge–Ampère equation. Numer. Math. 141(1), 253–288 (2019)MathSciNetMATHCrossRef
57.
Oberman, A.M.: Wide stencil finite difference schemes for the elliptic Monge–Ampere equation and functions of the eigenvalues of the hessian. Discrete Contin. Dyn. Syst. B 10(1), 221 (2008)MathSciNetMATH
58.
Safonov, M.V.: Nonuniqueness for second-order elliptic equations with measurable coefficients. SIAM J. Math. Anal. 30(4), 879–895 (1999)MathSciNetMATHCrossRef
59.
Seibold, B.: Minimal positive stencils in meshfree finite difference methods for the Poisson equation. Comput. Methods Appl. Mech. Eng. 198(3–4), 592–601 (2008)MathSciNetMATHCrossRef
60.
61.
Smears, I., Suli, E.: Discontinuous Galerkin finite element approximation of nondivergence form elliptic equations with Cordes coefficients. SIAM J. Numer. Anal. 51(4), 2088–2106 (2013)MathSciNetMATHCrossRef
62.
Tian, X., Du, Q.: Asymptotically compatible schemes and applications to robust discretization of nonlocal models. SIAM J. Numer. Anal. 52, 1641–1665 (2014)MathSciNetMATHCrossRef
63.
Tornberg, A.K., Engquist, B.: Regularization techniques for numerical approximation of PDEs with singularities. J. Sci. Comput. 19, 527–552 (2003)MathSciNetMATHCrossRef
64.
Trask, N., You, H., Yu, Y., Parks, M.L.: An asymptotically compatible meshfree quadrature rule for nonlocal problems with applications to peridynamics. Comput. Methods Appl. Mech. Eng. 343, 151–165 (2019)MathSciNetMATHCrossRef
65.
Trudinger, N.S., Wang, X.J.: The Monge–Ampere equation and its geometric applications. Handb. Geom. Anal. 1, 467–524 (2008)MathSciNetMATH
66.
Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik Crelles J. 1908(134), 198–287 (1908)MathSciNetMATHCrossRef
67.
Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. premier mémoire. sur quelques propriétés des formes quadratiques positives parfaites. Journal für die reine und angewandte Mathematik Crelles J. 1908(133), 97–102 (1908)MATHCrossRef
68.
Van der Vorst, H.A.: Bi-cgstab: a fast and smoothly converging variant of bi-cg for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 13(2), 631–644 (1992)MathSciNetMATHCrossRef
69.
Wendland, H.: Scattered Data Approximation, vol. 17. Cambridge University Press, Cambridge (2004)MATHCrossRef
Metadata
Title
Monotone Meshfree Methods for Linear Elliptic Equations in Non-divergence Form via Nonlocal Relaxation
Authors
Qihao Ye
Xiaochuan Tian
Publication date
01-09-2023
Publisher
Springer US
Published in
Journal of Scientific Computing / Issue 3/2023
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-023-02294-3

Other articles of this Issue 3/2023

Journal of Scientific Computing 3/2023 Go to the issue

OriginalPaper

Reformulated Dissipation for the Free-Stream Preserving of the Conservative Finite Difference Schemes on Curvilinear Grids

OriginalPaper

A Meshfree Collocation Scheme for Surface Differential Operators on Point Clouds

OriginalPaper

Analysis of a New Accelerated Waveform Relaxation Method Based on the Time-Parallel Algorithm

OriginalPaper

A Modified Convective Formulation in Navier–Stokes Simulations

OriginalPaper

Cauchy Noise Removal via Convergent Plug-and-Play Framework with Outliers Detection

OriginalPaper

Computation of Fractional Derivatives of Analytic Functions

Premium Partner

    Image Credits