A fast object-oriented MATLAB implementation of the reproducing kernel particle method. (English) Zbl 1398.74450

Summary: Novel numerical methods, known as Meshless Methods or Meshfree Methods and, in a wider perspective, Partition of Unity Methods, promise to overcome most of disadvantages of the traditional finite element techniques. The absence of a mesh makes meshfree methods very attractive for those problems involving large deformations, moving boundaries and crack propagation. However, meshfree methods still have significant limitations that prevent their acceptance among researchers and engineers, namely the computational costs. This paper presents an in-depth analysis of computational techniques to speed-up the computation of the shape functions in the Reproducing Kernel Particle Method and Moving Least Squares, with particular focus on their bottlenecks, like the neighbour search, the inversion of the moment matrix and the assembly of the stiffness matrix. The paper presents numerous computational solutions aimed at a considerable reduction of the computational times: the use of \(kd-\)trees for the neighbour search, sparse indexing of the nodes-points connectivity and, most importantly, the explicit and vectorized inversion of the moment matrix without using loops and numerical routines.


74S30 Other numerical methods in solid mechanics (MSC2010)
74S05 Finite element methods applied to problems in solid mechanics
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
76M25 Other numerical methods (fluid mechanics) (MSC2010)
76N10 Existence, uniqueness, and regularity theory for compressible fluids and gas dynamics


Mfree2D; Matlab; ESFLIB
Full Text: DOI


[1] Barbieri E, Meo M (2009) Evaluation of the integral terms in reproducing kernel methods. Comput Methods Appl Mech Eng 198(33–36): 2485–2507 · Zbl 1228.74109
[2] Belytschko T, Fleming M (1999) Smoothing, enrichment and contact in the element-free Galerkin method. Comput Struct 71(2): 173–195
[3] Belytschko T, Tabbara M (1996) Dynamic fracture using element-free Galerkin methods. Int J Numer Methods Eng 39(6): 923–938 · Zbl 0953.74077
[4] Belytschko T, Gu L, Lu Y (1994) Fracture and crack growth by element-free Galerkin methods. Model Simul Mater Sci Eng 2: 519–534
[5] Belytschko T, Lu Y, Gu L (1994) Element-free Galerkin methods. Int J Numer Methods Eng 37(2): 229–256 · Zbl 0796.73077
[6] Belytschko T, Lu Y, Gu L (1995) Crack propagation by element-free Galerkin methods. Eng Fract Mech 51(2): 295–315
[7] Belytschko T, Lu Y, Gu L, Tabbara M (1995) Element-free Galerkin methods for static and dynamic fracture. Int J Solids Struct 32(17): 2547–2570 · Zbl 0918.73268
[8] Belytschko T, Krongauz Y, Fleming M, Organ D, Liu WS (1996) Smoothing and accelerated computations in the element free Galerkin method. J Comput Appl Math 74(1): 111–126 · Zbl 0862.73058
[9] Belytschko T, Krongauz Y, Organ D, Fleming M, Krysl P (1996) Meshless methods: an overview and recent developments. Comput Methods Appl Mech Eng 139(1–4): 3–47 · Zbl 0891.73075
[10] Breitkopf P, Rassineux A, Touzot G, Villon P (2000) Explicit form and efficient computation of MLS shape functions and their derivatives. Int J Numer Methods Eng 48(451): 466 · Zbl 0965.65015
[11] Cartwright C, Oliveira S, Stewart D (2001) A parallel quadtree algorithm for efficient assembly of stiffness matrices in meshfree Galerkin methods. In: Proceedings of the 15th international parallel and distributed processing symposium, pp 1194–1198
[12] Chen J, Pan C, Wu C, Liu W (1996) Reproducing kernel particle methods for large deformation analysis of non-linear structures. Comput Methods Appl Mech Eng 139(1–4): 195–227 · Zbl 0918.73330
[13] Chen J, Pan C, Wu C (1997) Large deformation analysis of rubber based on a reproducing kernel particle method. Comput Mech 19(3): 211–227 · Zbl 0888.73073
[14] Collier N, Simkins D (2009) The quasi-uniformity condition for reproducing kernel element method meshes. Comput Mech 44(3): 333–342 · Zbl 1166.74048
[15] Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge · Zbl 1047.68161
[16] Dolbow J, Belytschko T (1998) An introduction to programming the meshless element free Galerkin method. Arch Comput Methods Eng 5(3): 207–241
[17] Duarte C (1995) A review of some meshless methods to solve partial differential equations. TICAM Report 95-06
[18] Fasshauer G (2007) Meshfree approximation methods with Matlab. World Scientific Publishing Co. Inc., River Edge · Zbl 1123.65001
[19] Finkel R, Bentley J (1974) Quad trees a data structure for retrieval on composite keys. Acta Inform 4(1): 1–9 · Zbl 0302.68055
[20] Fries T, Matthies H (2004) Classification and overview of meshfree methods. Informatikbericht Nr. 2003-3, Scientific Computing University · Zbl 1354.76105
[21] Griebel M, Schweitzer M (2002) A particle-partition of unity method–part II: efficient cover construction and reliable integration. SIAM J Sci Comput 23(5): 1655–1682 · Zbl 1011.65069
[22] Idelsohn S, Oñate E (2006) To mesh or not to mesh. That is the question. Comput Methods Appl Mech Eng 195(37–40): 4681–4696 · Zbl 1118.74051
[23] Klaas O, Shephard M (2000) Automatic generation of octree-based three-dimensional discretizations for partition of unity methods. Comput Mech 25(2): 296–304 · Zbl 0956.65113
[24] Krysl P, Belytschko T (2001) ESFLIB: a library to compute the element free Galerkin shape functions. Comput Methods Appl Mech Eng 190(15–17): 2181–2206 · Zbl 1013.74080
[25] Lancaster P, Salkauskas K (1981) Surfaces generated by moving least squares methods. Math Comput 37(155): 141–158 · Zbl 0469.41005
[26] Li S, Liu W (1996) Moving least-square reproducing kernel method part II: Fourier analysis. Comput Methods Appl Mech Eng 139(1–4): 159–193 · Zbl 0883.65089
[27] Li S, Liu W (2004) Meshfree particle methods. Springer, Berlin · Zbl 1073.65002
[28] Libersky L, Petschek A (1990) Smooth particle hydrodynamics with strength of materials. In: Proceedings of the next free-Lagrange conference, June 1990, Jackson Lake Lodge, Moran, Wyoming · Zbl 0791.76066
[29] Libersky L, Petschek A, Carney T, Hipp J, Allahdadi F (1993) High strain Lagrangian hydrodynamics: a three-dimensional SPH code for dynamic material response. J Comput Phys 109(1): 67–75 · Zbl 0791.76065
[30] Liu G (2003) Mesh free methods: moving beyond the finite element method. CRC Press, Boca Raton · Zbl 1031.74001
[31] Liu G, Tu Z (2002) An adaptive procedure based on background cells for meshless methods. Comput Methods Appl Mech Eng 191(17–18): 1923–1943 · Zbl 1098.74738
[32] Liu W, Jun S, Zhang Y (1995) Reproducing kernel particle methods. Int J Numer Methods Fluids 20(8–9): 1081–1106 · Zbl 0881.76072
[33] Liu W, Chen Y, Uras R, Chang C (1996) Generalized multiple scale reproducing kernel particle methods. Comput Methods Appl Mech Eng 139(1–4): 91–157 · Zbl 0896.76069
[34] Liu W, Hao W, Chen Y, Jun S, Gosz J (1997) Multiresolution reproducing kernel particle methods. Comput Mech 20(4): 295–309 · Zbl 0893.73078
[35] Liu W, Li S, Belytschko T (1997) Moving least-square reproducing kernel methods. (I) Methodology and convergence. Comput Methods Appl Mech Eng 143(1–2): 113–154 · Zbl 0883.65088
[36] Lucy L (1977) A numerical approach to the testing of the fission hypothesis. Astron J 82(12): 1013–1024
[37] Macri M, De S, Shephard M (2003) Hierarchical tree-based discretization for the method of finite spheres. Comput Struct 81(8–11): 789–803
[38] Monaghan J (1982) Why particle methods work. SIAM J Sci Stat Comput 3: 422 · Zbl 0498.76010
[39] Monaghan J (1988) An introduction to SPH. Comput Phys Commun 48(1): 89–96 · Zbl 0673.76089
[40] Monaghan J (1992) Smoothed particle hydrodynamics. Annu Rev Astron Astrophys 30(1): 543–574
[41] Moore A (1991) A tutorial on kd-trees. University of Cambridge Computer Laboratory. Technical Report No. 209. Extract from PhD thesis. http://www.autonlab.org/autonweb/14665.html
[42] Nguyen V, Rabczuk T, Bordas S, Duflot M (2008) Meshless methods: a review and computer implementation aspects. Math Comput Simul 79: 763–813 · Zbl 1152.74055
[43] Rabczuk T, Belytschko T (2005) Adaptivity for structured meshfree particle methods in 2D and 3D. Int J Numer Methods Eng 63(11): 1559–1582 · Zbl 1145.74041
[44] Shaofan L, Liu W (2002) Meshfree and particle methods and their applications. Appl Mech Rev 55: 1–34
[45] Tabarraei A, Sukumar N (2005) Adaptive computations on conforming quadtree meshes. Finite Elements Anal Des 41(7–8): 686–702 · Zbl 1173.74444
[46] You Y, Chen J, Lu H (2003) Filters, reproducing kernel, and adaptive meshfree method. Comput Mech 31(3): 316–326 · Zbl 1038.74681
[47] Zhou J, Wang X, Zhang Z, Zhang L (2005) Explicit 3-D RKPM shape functions in terms of kernel function moments for accelerated computation. Comput Methods Appl Mech Eng 194(9–11): 1027–1035 · Zbl 1137.74453
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.