Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barbieri E, Meo M (2009) Evaluation of the integral terms in reproducing kernel methods. Comput Methods Appl Mech Eng 198(33–36): 2485–2507
Belytschko T, Fleming M (1999) Smoothing, enrichment and contact in the element-free Galerkin method. Comput Struct 71(2): 173–195
Belytschko T, Tabbara M (1996) Dynamic fracture using element-free Galerkin methods. Int J Numer Methods Eng 39(6): 923–938
Belytschko T, Gu L, Lu Y (1994) Fracture and crack growth by element-free Galerkin methods. Model Simul Mater Sci Eng 2: 519–534
Belytschko T, Lu Y, Gu L (1994) Element-free Galerkin methods. Int J Numer Methods Eng 37(2): 229–256
Belytschko T, Lu Y, Gu L (1995) Crack propagation by element-free Galerkin methods. Eng Fract Mech 51(2): 295–315
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
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
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
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
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
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
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
Collier N, Simkins D (2009) The quasi-uniformity condition for reproducing kernel element method meshes. Comput Mech 44(3): 333–342
Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge
Dolbow J, Belytschko T (1998) An introduction to programming the meshless element free Galerkin method. Arch Comput Methods Eng 5(3): 207–241
Duarte C (1995) A review of some meshless methods to solve partial differential equations. TICAM Report 95-06
Fasshauer G (2007) Meshfree approximation methods with Matlab. World Scientific Publishing Co. Inc., River Edge
Finkel R, Bentley J (1974) Quad trees a data structure for retrieval on composite keys. Acta Inform 4(1): 1–9
Fries T, Matthies H (2004) Classification and overview of meshfree methods. Informatikbericht Nr. 2003-3, Scientific Computing University
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
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
Klaas O, Shephard M (2000) Automatic generation of octree-based three-dimensional discretizations for partition of unity methods. Comput Mech 25(2): 296–304
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
Lancaster P, Salkauskas K (1981) Surfaces generated by moving least squares methods. Math Comput 37(155): 141–158
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
Li S, Liu W (2004) Meshfree particle methods. Springer, Berlin
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
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
Liu G (2003) Mesh free methods: moving beyond the finite element method. CRC Press, Boca Raton
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
Liu W, Jun S, Zhang Y (1995) Reproducing kernel particle methods. Int J Numer Methods Fluids 20(8–9): 1081–1106
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
Liu W, Hao W, Chen Y, Jun S, Gosz J (1997) Multiresolution reproducing kernel particle methods. Comput Mech 20(4): 295–309
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
Lucy L (1977) A numerical approach to the testing of the fission hypothesis. Astron J 82(12): 1013–1024
Macri M, De S, Shephard M (2003) Hierarchical tree-based discretization for the method of finite spheres. Comput Struct 81(8–11): 789–803
Monaghan J (1982) Why particle methods work. SIAM J Sci Stat Comput 3: 422
Monaghan J (1988) An introduction to SPH. Comput Phys Commun 48(1): 89–96
Monaghan J (1992) Smoothed particle hydrodynamics. Annu Rev Astron Astrophys 30(1): 543–574
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
Nguyen V, Rabczuk T, Bordas S, Duflot M (2008) Meshless methods: a review and computer implementation aspects. Math Comput Simul 79: 763–813
Rabczuk T, Belytschko T (2005) Adaptivity for structured meshfree particle methods in 2D and 3D. Int J Numer Methods Eng 63(11): 1559–1582
Shaofan L, Liu W (2002) Meshfree and particle methods and their applications. Appl Mech Rev 55: 1–34
Tabarraei A, Sukumar N (2005) Adaptive computations on conforming quadtree meshes. Finite Elements Anal Des 41(7–8): 686–702
You Y, Chen J, Lu H (2003) Filters, reproducing kernel, and adaptive meshfree method. Comput Mech 31(3): 316–326
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
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Barbieri, E., Meo, M. A fast object-oriented Matlab implementation of the Reproducing Kernel Particle Method. Comput Mech 49, 581–602 (2012). https://doi.org/10.1007/s00466-011-0662-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00466-011-0662-x