betaFeedback

WorksMathematics

An Overview of Meshfree Collocation Methods

Abstract

We provide a comprehensive overview of meshfree collocation methods for numerically approximating differential operators on continuously labeled unstructured point clouds. Meshfree collocation methods do not require a computational grid or mesh. Instead, they approximate smooth functions and their derivatives at potentially irregularly distributed collocation points, often called particles, to a desired order of consistency. We review several meshfree collocation methods from the literature, trace the historical development of key concepts, and propose a classification of methods according to their principle of derivation. Although some of the methods reviewed are similar or identical, there are subtle yet important differences between many, which we highlight and discuss. We present a unifying formulation of meshfree collocation methods that renders these differences apparent and show how each method can be derived from this formulation. Finally, we propose a generalized derivation for meshfree collocation methods going forward.

Nomenclature

We use bold symbols for vectors and tensors. Vectors are in bold mathtype, whereas matrices and tensors are in bold upright roman. We use uppercase Latin letters for vectors of dimension pp (the number of coefficients/weights in the discrete operator); Vectors of other dimensions are in lowercase. We use lowercase Latin letters for vector or tensor element indices (in row-major ordering), and lowercase Greek letters for coordinate directions. The most important symbols are defined as follows:

Symbols

SymbolDescription
α\alpha, β\beta, γ\gamma, …\ldotsindices used to index individual spatial components
α\alphamulti-index
UiU_ivector containing values of function uu for all neighbors of particle ii
λ\lambdaLagrange multipliers [-]
λ\lambdaLagrange multipliers [-]
Ψiα\Psi_i^\alphavector of weight coefficients used to construct weight functions
BiαB_i^\alphavector of moments of weight functions wjidw_{ji}^{d}
DuD_uvector of all multi-index derivatives of variable ψ\psi up order of mm
EiE_ivector of reminders in Lagrange form for all neighbors of particle ii

Table 2.

HiH_i vector of inverse stencil size scales following Taylor monomial powers up to order of mm

PjiP_{ji} vector of basis functions evaluated between particles ii and jj

WW, WjiW_{ji}, WjiαW_{ji}^{\alpha} vector of Anisotropic Basis Functions (ABFs), single ABF

wiα\mathbf{w}_i^{\alpha} vector of weight functions for all neighbors of particle ii

XX, XjiX_{ji} vector of Taylor monomials assumed up to order of mm

δαβ\delta_{\alpha\beta} Kronecker delta

Bi\mathbb{B}_i matrix with rows corresponding to weight function moments for all the derivatives up to order of mm at particle ii

MiM_i moment matrix related to the particle ii [-]

N0n\mathbb{N}_0^n nn dimensional space of natural numbers including zero

Pm\mathbb{P}_m space of polynomials up to order of mm

Rn\mathbb{R}^n nn-dimensional set of real numbers

Vi\mathbf{V}_i diagonal matrix with diagonal entries Wji0W_{ji}^{0} for all neighbors of particle ii

Wi\mathbf{W}_i matrix with lines corresponding to WjiW_{ji} evaluated for all neighbors of particle ii

Yi\mathbf{Y}_i matrix with rows corresponding to weight coefficients for all the derivatives up to order of mm at particle ii

Ci\mathbf{C}_i matrix of weight functions for all derivatives up to order of mm for all neighbors of particle ii

x\mathbf{x}, xi\mathbf{x}_i spatial position, spatial coordinates of discretization node ii (or point/particles ii)

Xi\mathbf{X}_i matrix with lines corresponding to XjiX_{ji} evaluated for all neighbors of particle ii

Cd\mathbf{C}^d mapping vector which selects desired derivatives from vector of derivatives D(⋅)i\mathbf{D}(\cdot)_i

Dαu\mathcal{D}^{\alpha}u multi-index derivative of variable uu

JE,i\mathcal{J}_{E,i} functional for ℓ2\ell_2 minimization of approximation error [-]

JP,i\mathcal{J}_{P,i} functional for ℓ2\ell_2 minimization under the moment condition constraint [-]

JP,i\mathcal{J}_{P,i} functional for ℓ2\ell_2 minimization under the moment condition constraint [-]

JP,i\mathcal{J}_{P,i} generalized functional for ℓ2\ell_2 minimization under the moment condition constraint [-]

JP,i\mathcal{J}_{P,i} generalized functional for ℓ2\ell_2 minimization under the moment condition constraint [-]

Ni\mathcal{N}_i set of indices of nodes (or points/particles) neighboring with particle ii

O(h)\mathcal{O}(h) big O notation

P\mathcal{P} set of indices of all discretization nodes (or point/particles)

X\mathcal{X} set of spatial coordinates of all discretization nodes (or point/particles)

Ω\Omega, Ω‾\overline{\Omega}, ∂Ω\partial\Omega domain, closure of the domain, domain boundary

φji\varphi_{ji} radial basis function

C~α\widetilde{C}^{\alpha} rescaled mapping vector

X~ji\widetilde{X}_{ji} rescaled vector of Taylor monomials

dd differential operator

ejime_{ji}^{m} Lagrange form of the remainder between particles ii and jj of order mm

hh characteristic size of computational stencil

i,j,k,…i, j, k, \ldots indices of individual discretization nodes (or point/particles)

l(d)l(d) degree the differential operator dd

LidL_i^d general discrete differential operator (discretizing diff. op. dd)

mm order of the approximation

NN total number of discretization nodes (or points/particles)

nn space dimension

NiN_i number of nodes (or points/particles) neighboring with particle ii

pp, p2Dp_{2\mathrm{D}}, p3Dp_{3\mathrm{D}} number of elements in order and dimension dependent vectors, in 2D, in 3D

sis_i average node spacing inside the neighborhood Ni\mathcal{N}_i of node ii

uu, u(x)u(x), uiu_i general variable, g. v. evaluated at x, g. v. evaluated at xix_i

u∗u^* general function from space of polynomials

wjidw_{ji}^d weight functions of general discrete differential operator dd

Acronyms

B-PIM Boundary-Point Interpolation Method

CMLS Compact Moving Least Squares Method

D-EM Diffuse-Element Method

DC-PSE Discretization-Corrected Particle Strength Exchange

EFG Element Free Galerkin Method

FPDM Finite Difference Particle Method

FPM Finite Point Method

FPsM Finite Pointset Method

GFDM Generalized Finite-Difference Method

GMLS Generalized Moving Least Squares Method

GRKCM Gradient Reproducing Kernel Collocation Method

HOCSPH High-order Consistent SPH

IMLS Interpolating Moving Least Squares Method

IMMLS Interpolating Modified Moving Least Squares Method

KE Kernel Estimate

KGF Kernel Gradient Free

KMM Kinetic Meshfree Method

LDD Lagrangian Differencing Dynamics

LFDM Lagrangian Finite-Difference Method

LSCM Least Squares Collocation Meshless Method

LSKUM Least Squares Kinetic Upwind Method

LSMFM Least-Squares Meshfree Method

MFDM Meshfree Finite Difference Method

MLPG Local Petrov Galerkin Method

MLS Moving Least Squares

MMLS Modified Moving Least Squares Method

MPS Moving Particle Semi-Implicit

PDA Particle Derivative Approximation

PDE partial differential equations

PDM Particle Difference Method

PIC Particle-In-Cell

PIM Point Interpolation Method

PSE Particle Strength Exchange

PU Partition of Unity

RBCM Radial Basis Collocation Method

RKA Reproducing Kernel Approximations

RKCM Reproducing Kernel Collocation Method

RKPM Reproducing Kernel Particle Method

RMLS Regularized Moving Least Squares Method

SPH Smoothed Particle Hydrodynamics

WLS Weighted Least Squares

Introduction

We present an overview and classification of meshfree collocation methods. Meshfree collocation methods are a class of numerical methods for approximating strong-form solutions to partial differential equations (PDEs). They do so without requiring a computational grid or mesh, by discretizing the unknown continuous functions on a set of irregularly placed collocation points. The collocation points therefore form a point cloud, on which the differential operators occurring in the PDE are approximated. In meshfree collocation methods, this is done in the strong sense by directly approximating the derivatives themselves from the discretized function values. Therefore, meshfree collocation methods can be seen as a generalization of finite differences to irregularly distributed collocation points, or nodes.

In addition to being a generalization of finite differences to scattered nodes, meshfree collocation methods are also a special sub-class of the larger algorithmic family of particle methods, although “meshfree method” and “particle method” are sometimes used synonymously in the literature. Particle methods are a family of numerical algorithms in which point-like objects—called particles—interact pairwise and then evolve as a result of these interactions, as has been rigorously defined [182]. They are among the oldest and most computationally powerful numerical algorithms [183]. In a particle method, particles can represent discrete model entities, such as atoms in a molecular simulation [3, 190, 213], grains in simulations of granular materials [49, 51, 50, 240], or molecules or material elements in more coarse-grained models [94, 65, 84]. Alternatively, the particles in particle methods can also represent discretization elements or samples of a continuous field. This is the case, for example, for Smoothed Particle Hydrodynamics (SPH) simulations in astrophysics and fluid dynamics [82, 150, 166, 167], Particle-In-Cell (PIC) simulations in plasma physics [27] [66, 89, 6], and Vortex Methods for incompressible fluid flow [45, 132, 86, 47]. In all particle methods, the particles carry discrete or continuous properties, thus forming a labeled point cloud. The labeled point cloud in meshfree (sometimes also referred to as meshless) methods is one specific case [40]. Meshfree methods numerically approximate the solution of a PDE on particles that represent the individual discretization points. Then, the particles have positions in the continuous domain of solution of the PDE and continuous properties discretizing the unknown functions. Once the particle properties have been supplemented with appropriate boundary and/or initial conditions, the particles evolve in time so as to approximate the solution of the PDE. During time evolution, the particles can change either their positions, their properties, or both. Methods in which particle properties are dynamic, but their positions are constant, are referred to as Eulerian particle methods. If the particle positions (also) change over time, for example to track a flow field or a deforming domain geometry, particle methods are called Lagrangian.

Both Eulerian and Lagrangian particle methods are meshfree numerical methods for continuous PDE problems. They can be formulated to approximate the solution of the PDE in either the strong or the weak sense. Meshfree Galerkin methods discretize the weak form of PDE. Even though they are not the topic of this article, we briefly mention them here for completeness. Meshfree Galerkin methods originated from the Diffuse-Element Method (D-EM)1 as a generalization of the finite element method [171]. A meshfree Wavelet Galerkin method was proposed by Amaratunga et al. [5]. Shortly thereafter Belytschko [19] [18] and Lu [148] introduced the Element Free Galerkin method (EFG), improving over the original D-EM. In the late 1990s, meshfree Galerkin methods based on Partition of Unity (PU) were introduced by Babuška and Melenk [9, 157] and by Durate and Lizska [61, 142], known as hp-clouds. Most recently, the meshfree Local Petrov Galerkin Method (MLPG) has been introduced by Atluri et al. [8, 7]. In meshfree Galerkin methods, the particles carry (weighted) basis functions and integration volumes of the weak-form PDE solution.

In contrast to meshfree Galerkin methods, the particles in meshfree collocation methods are volume-less points [223] that directly sample the function values at the given locations, thus discretizing the strong form of the PDE. In this text, we provide an overview of meshfree collocation methods. For this class of numerical methods, we provide a unifying mathematical definition and show how all reviewed methods adhere to this definition for certain design choices. This makes explicit the differences between methods, but also shows under what conditions they are equivalent. In doing so, we bridge diverse nomenclatures, as different methods were developed by different scientific communities—such as solid mechanics, fluid mechanics, or applied mathematics—each using different terminology. This also led to several methods being re-invented under different names over time, while others were independently derived using novel approaches. We hope we have succeeded in collecting most of the existing methods. We classify all reviewed methods into four groups according to the mathematical principle underlying their derivation. Thereby, we hope to clarify equivalence, differences, and characteristics of meshfree collocation methods.

To better understand the mathematical basis and commonalities of meshfree collocation methods, we start by giving an overview of their historic development.

A brief history of meshfree collocation methods

Meshfree collocation methods are historically rooted in works on function approximation and interpolation on scattered points from the early twentieth century [128, 74, 212]. The foundational reference specifically using these ideas for collocation methods is MacNeal, 1953 [151]. Studying second-order boundary-value problems with curved boundary, MacNeal generalized finite differences to allow for determining weights for arbitrarily distributed nodes from a linear system of equations. This still is the basic concept underlying meshfree collocation methods today.

The concept of finite differences on scattered nodes was later discussed by Shepard in his work on interpolation of scattered data [204]. The function-approximation side of the problem was much later considered by Wendland in his seminal book on scattered data approximation [245]. Wendland’s book addresses both the theoretical foundation and the practical applications of meshfree approximation, spanning from numerical analysis to computer graphics.

Focusing on numerical analysis and the approximation of differential operators in meshfree collocation methods, MacNeal’s pioneering work [151] was generalized and formalized by Forsyth and Wasow [69] and by Swartz and Wendroff [224]. Meshfree collocation methods as we know them today were first formulated by Jensen [102], where also the neighbor search procedure was given attention.

Indeed, an important early difficulty for meshfree collocation methods was to efficiently find the neighbors of a point when constricting and evaluating the stencils [187]. The stencil, also sometimes referred to as “star” is the set of all neighboring points a given point needs to know the values of in order to build its local approximation. Constructing the stencil without having to search over all points, especially in Lagrangian discretizations where points move, became efficiently possible thanks to fast neighbor-search algorithms like cell lists [93] and Verlet lists [239]. The problem remained, though, to choose for each point the correct number of neighbors such that the linear system of equations for the stencil weights is determined.

The constraint of working with determined linear systems was relaxed in the early 1980s with the introduction of Moving Least Squares (MLS) approximation methods [126, 127]. The concept of MLS had been inspired by the earlier work of Shepard [204] and, notably, MacLain [155, 156, 10, 83, 71] on irregular data interpolation. This extended the original method of Jensen [102] to considering more stencil points than the number of unknowns in the linear system, resulting in overdetermined stencil systems, as introduced by Liszka and Orkisz [143, 141]. The works by Liszka and Orkisz are therefore widely regarded as foundational for today’s meshfree collocation methods.

In parallel, and since the 1970s, alternative methods have been developed to approximate functions and their derivatives on scattered points. Monaghan and Gingold [82], and independently Lucy [150], introduced SPH, originally for applications in astrophysics, which brought the concept of a Kernel Estimate (KE). A few years later, Chen and Liu elaborated on this concept, introducing the Reproducing Kernel Particle Method (RKPM) [41, 146]. This was based on imposing a reproducing condition on the approximation kernels, with the aim of improving the accuracy of SPH. Another alternative approach is the Radial Basis Collocation method (RBCM) introduced by Kansa [110, 111], where radial basis functions are used to approximate the non-trivial domain integration problem.

Within the class of MLS-like methods, development continued with the Generalized Moving Least Squares Method (GMLS) introduced in the late 1990s [133]. GMLS is not limited to approximating differential operators, but is able to handle more general operators on a Banach space [245, 164, 163, 85]. It is often formulated in more rigorous mathematical language [163, 85, 165]. The connection between GMLS and RKPM was investigated in Ref. [15], and the connection between GMLS and RBF-FD was established in Ref. [108].

In summary, meshfree collocation methods have a long history. While mostly rooted in interpolation and approximation of scattered data, novel and original ideas have emerged over time. Some came from studying the numerical properties of the methods, some were inspired by particular applications. More recently, there is a clear trend to bridge across methods, study their mathematical connections, and generalize the theory. This is what we attempt in the remainder of this paper for meshfree collocation methods.

Methods reviewed in this paper

Meshfree collocation methods can roughly be divided into MLS-type methods and generalized finite-difference methods (GFDM). The former relate to the idea of operating on local least-squares regression approximations, whereas the latter take the more discrete viewpoint of weighted point-cloud stencils.

Modern MLS-type methods include Compact MLS (CMLS) [232], which introduced additional penalization terms to the MLS approximation that are specific to the PDE being solved. Modified MLS (MMLS) [107, 106] introduced additional terms based on the coefficients of the local approximation polynomials to automatically reduce the order of the approximation when not enough particles are available in the neighborhood. The idea penalized MLS penalties was formalized in Regularized MLS (RMLS) [242]. In the class of interpolating MLS methods, where the weight function is required to additionally satisfy a Kronecker delta property, Interpolating Modified MLS (IMMLS) [147] generalized Interpolating MLS (IMLS) [127] in the same way as MMLS generalized the original MLS. This was further extended GMLS to discretizing arbitrary linear bounded operators [133]. The numerical stability of these methods in time stepping was enhanced by the Adaptive Orthogonal Improved Interpolating MLS method [243]. Linking MLS and finite-difference approaches, the Least-Squares Meshfree Method (LSMFM) [185, 257] was introduced, which uses a meshfree finite difference based on a MLS approximation.

GFDM trace back to the works of Jensen [102] and Perrone and Kao [187], followed by significant advancements by Liszka and Orkisz [143, 141, 97], eventually bridging them with MLS techniques [127]. More recent works [221, 216, 220] broadened the scope of GFDM and showed the formal connections between the methods in this class, including the Finite Point Method (FPM) [180], Finite Pointset Method (FPsM) [226]2, the Meshless Local Strong Form Method (MLSM) [118], Weighted Least Squares (WLS) [198], and Least Squares Collocation Meshless Method (LSCM) [256]. Applications of GFDM include incompressible and free-surface flows [255, 222], phase transitions [218, 129], geophysics [169], soil mechanics [158, 118], advection-diffusion problems [189], shallow-water and thin-film flows [134, 135, 217], multiphase flow [25] [252, 104], sub-surface flow [159, 251, 42], nonlinear obstacle problems [33], wave propagation [35] [253, 246], inverse problems [67, 136], and PDEs on curved surfaces [103, 220, 219]. Comprehensive numerical analysis and error estimation is available for GFDMs [53, 54, 258]. The origins of GFDM for Lagrangian incompressible flow simulations are associated with FPsM [125, 124], whereas FPM [180, 179] was mostly developed for compressible flows in an Eulerian discretization [176, 254], hyperbolic conservation laws [76], and free-surface flows [197]. Despite this difference in their application, FPM and FSPM are mathematically identical in how they approximate derivatives.

A collocation version of RKPM, which avoids numerical quadrature, was introduced with the Reproducing Kernel Collocation Method (RKCM) [4]. Similar to MLS, RKCM first approximates the function itself, but the derivatives are obtained as full derivatives of the function approximation. A simplified derivative approximation is used in the Gradient Reproducing Kernel Collocation Method (GRKCM) [44], which corresponds to GFDM based on a MLS approximation.

Another sub-class of GFDM originates from the Finite Difference Particle Method (FDPM) for wave problems [244], which uses a variable smoothing length over Lagrangian particles. This approach is similar to that of the Particle Difference Method (PDM) [249] and the Particle Derivative Approximation (PDA) [248]. The Meshless Local Strong Form Method (MLSM) [118] is based on similar principles but provides a link to meshfree Galerkin methods. The same idea can also be found under the name Meshfree Finite Difference Method (MFDM) in solid mechanics [160]. However, MFDM provides an original way to construct higher-order approximations without inverting complete moment matrices [161, 162].

A meshfree collocation method that links both MLS-type and GFDM-type methods is Discretization-Corrected Particle Strength Exchange (DC-PSE) [200]. Its derivation was motivated by the approximation errors of the classic Particle Strength Exchange (PSE) method [55, 63], which prevented PSE from converging on asymmetric particle distributions. Inspired by earlier works on discretization correction for particle methods [21] [46, 91], DC-PSE results in a general formulation in which SPH, GFDM, MLS, RKPM, and grid-based finite differences are included as special cases [200, 202]. DC-PSE has been successfully used to solve incompressible flow problems [30] [208], problems in solid mechanics [101, 259], and biological active hydrodynamics [209, 210, 2]. The method was also extended to solving PDEs on curved surfaces [206].

One of the most recent variants of GFDMs is the Local Anistropic Basis Function Method (LABFM) [115, 114]. Despite its name, it follows directly from the methods introduced so far, and it is not to be confused with particle methods employing anisotropic kernels for direction-dependent adaptive resolution [87]. Mathematically, LABFM is almost identical to DC-PSE but uses a different construction for the weight functions. In LABFM, weight functions are generated by orthogonal polynomials [114], which has clear advantages over the Taylor monomial basis used in DC-PSE. LABFM so far has mostly been used for direct numerical simulation of combustion [116] and for viscoelastic flows [117], both in complex geometries.

In addition to MLS-type and GFDM-based methods, there are specialized meshfree collocation methods that were not originally designed to approximate derivatives. Instead, they are physics-inspired and usually targeted at a specific PDE or application. These methods take an intermediate position between a phenomenological simulation method and a numerical solver. This includes methods such as the Least Squares Kinetic Upwind Method (LSKUM) [79], its variant q-LSKUM [80], and the Kinetic meshfree Method (KMM) [188], all designed to solve inviscid compressible flows and supersonic flows [79]. All three methods derive from the Boltzmann transport equation by taking statistical moments in an Eulerian coordinate system. Meshfree finite differences are then used to compute the fluxes from these moments.

Another group of physics-informed GFDM comprises the Lagrangian Finite-Difference Method (LFDM) [11, 12, 13] and Lagrangian Differencing Dynamics (LDD) [186]. Motivated by discretizing the Laplace operator using SPH, and inspired by correction schemes based on Taylor expansion, these methods focus on first and second derivatives, introducing different formulations of correction matrices. These correction matrices are usually smaller than the matrices obtained from MLS-based schemes, which makes LFDM and LDD especially suitable for Lagrangian simulations, where the matrices have to be recomputed at each time step. The authors describe these methods as “a balance between oscillatory but faster SPH and Moving Particle Semi-Implicit (MPS) methods, and accurate but slower MLS-based methods” [13]. Applications of these methods focus on the incompressible Navier-Stokes equation in Lagrangian form. However, LDD was also used for mean-field granular flows [186], viscoelastic flows [14], and fluid-structure interaction [184].

As is made evident in the context of LDD, meshfree collocation approaches are also commonly found within other particle methods, which are not strictly collocation methods themselves. For SPH, this includes a large family of kernel correction methods that aim to make the derivative approximation in SPH higher-order consistent by introducing MLS-based correction matrices. This includes the Kernel Gradient Free (KGF) method [95], the correction method by Randles and Libersky [192] and Bonet and Look [28], High-Order Consistent SPH (HOC-SPH) [170], and several others [194, 250, 130, 88]. Other examples of method that include meshfree collocation are remeshed particle methods [119, 48, 37], where meshfree collocation approaches are often used to interpolate the function values from irregularly distributed particles to a regular Cartesian grid on which the derivatives are then approximated using finite differences [153]. This remeshing approach is frequently used in Vortex-Particle methods for incompressible flows [119, 38], but also in SPH [36, 91] and in Wavelet Particle methods [22].

In addition to using meshfree collocation as a correction to ensure convergence of other particle methods, there is also a methodologically interesting connection with state-based peridynamics. State-based peridynamics presents an alternative formulation of continuum mechanics by introducing non-local forces in order to deal with large deformations and material separation [205, 152]. There, the divergence of the stress tensor is replaced with an integral formulation of the action potential of the forces. Upon discretizing the integral by a numerical quadrature, this leads to a meshfree collocation method for the force calculation. It is therefore not surprising that there have been attempts to connect peridynamics operators with other, more canonical, meshfree collocation formulations [23] [92].

Taken together, there is a plethora of modern meshfree collocation methods in the literature today. While, as we have outlined in Section 1.1, they all derive from a few common ancestors, they often diverged since then as they were developed by different scientific communities. For example, the methods used in computational fluid dynamics (notably, GFDM, DC-PSE, LDD, LABFM) are disjoint from the methods used in solid mechanics (RKPM, GRKCM, MFDM). While many of the methods are somewhat heuristic, rigorous numerical analysis is available for some of them, notably for GMLS, RKCM, and DC-PSE3. What stands out is that despite the diversity of methods presented in the literature, they are all based on common numerical principles and share many algorithmic properties. Understanding how all of these methods map onto one another could help translate algorithmic improvements and numerical analysis results from one method to the others. This is the main motivation for this paper. But before we present a unifying mathematical formulation for all meshfree collocation methods, we briefly highlight available software implementations and software libraries that can be used to implement meshfree collocation methods.

Notable software implementations

Many software libraries and codes implement meshfree collocation methods. While it is impossible to enumerate them all, we here provide a brief list of notable implementations with the purpose of highlighting the availability of the methods and the level of support for practical applications. Some of these software implementation specifically provide meshfree PDE solvers, whereas others are more general particle methods frameworks within which meshfree collocation have been implemented. Also, some of these codes are available as open-source free software, whereas others are commercially distributed or closed-source.

A generic open-source framework for particle methods is OpenFPM [100], developed by the MOSAIC Group at Dresden University of Technology and the Max Planck Institute of Molecular Cell Biology and Genetics [168]. The Open Framework for Particles and Meshes, OpenFPM, provides a generic abstraction layer for implementing particles-only and hybrid particle–mesh codes on parallel computer systems. It uses compile-time code generation to support different hardware platforms, ranging from multi-core CPUs, over distributed-memory clusters, to Graphics Processing Units (GPUs) and distributed multi-GPU clusters [99]. In its numerics module, among several other solvers, OpenFPM provides implementations of DC-PSE [200] and Surface DC-PSE [206] with a convenient template expression system for near-mathematical PDE notation [207].

A comprehensive open-source toolkit for numerical computation on point clouds is provided by Compadre [122], which is developed as part of the TRILINOS project [233] for scientific computing. Compadre focuses on assembly of the systems of equations for the stencil coefficients in meshfree collocation methods. It therefore excels at handling small dense matrices. For other parts of a meshfree collocation solver, such as for inverting the large sparse matrix of the global system, and for neighbor search, Compadre relies on other components of the TRILINOS ecosystem. In the same spirit, Compadre supports performance portability across different hardware platforms and GPUs through the Kokkos core package of TRILINOS [234]. Besides providing a generic computational toolkit, Compadre also implements the GMLS meshfree collocation method, both in bulk and on curved surfaces.

A more targeted open-source implementation of meshfree collocation methods for PDEs is Medusa [211, 109]. Medusa implements a range of methods, including FPM, GFDM, WLS, RBF-FD, and MLSM under a single code framework. It provides wide range of predefined differential operators that can be used to straightforwardly discretize PDEs.

A compact stand-alone open-source implementation of the FPsM is provided by the gfdm-Toolkit [225]. It supports two-dimensional simulations of incompressible hydrodynamics, linear elasticity, and heat conduction. Finally, mFDlab [52] is an open-source collection of MATLAB functions for developing and testing meshfree collocation methods. While it supports implementing arbitrary meshfree collocation methods, RBF-FD and a range of MLS-type methods come predefined.

Complementing open-source implementations, there are commercial codes for meshfree collocation methods. Among them is MESHFREE [73] by the Fraunhofer Institute for Industrial Mathematics, implementing GFDM and FPsM for problems from fluid and continuum mechanics. MESHFREE enables simulations of free-surface flows, multiphase flows, non-Newtonian flows [238], as well as problems with large deformations and moving boundaries. It supports incompressible, weakly compressible, and compressible flows regimes on parallel computing platforms. Coupling options include the Discrete Element Method (DEM), rigid-body solvers, and discrete phase models [24, 26] within the software, as well as with several external structural mechanics software for fluid-structure interaction.

Another commercial code that includes meshfree collocation methods is VPS (formerly PAM-CRASH) by the ESI Group [64]. While VPS is primarily a finite-element code for crash and impact simulations, it also implements the FPsM in a dedicated meshfree collocation module [231, 123]. This module originated as a branch of MESHFREE and is mostly applied to fluid–structure interaction problems.

A third commercial code for meshfree collocation methods is Points by NOGRID GmbH [174], which likewise originated as a branch of MESHFREE. Points implements the FPsM for problems across a broad spectrum of computational fluid mechanics. It is able to solve problems with coupled heat and mass transfer, as well as with plastic and elastic material properties.

Another commercial meshfree collocation methods software focusing on fluid mechanics applications is RHOXYZ [196], which is developed in collaboration with the University of Split, Croatia. RHOXYZ implements the LDD method with a focus on solving incompressible flow problems in a Lagrangian frame, also supporting GPU acceleration. The core solver is supplemented with fluid-structure interaction and with coupling to external Finite Element and Discrete Element solvers.

Previous overview texts

Before delving into the mathematical framework and classification of meshfree collocation methods, we provide a guide to previous review and overview articles as well as books on meshfree methods, in chronological order.

  • The early development of meshfree collocation methods has been comprehensively summarized by Franke, 1977 [72], and compared with other early techniques for scattered data in 1982 [70].

  • Duarte, 1995 [60], presented an authoritative overview of meshfree Galerkin methods, covering MLS approaches, D-EM, EFG, Kernel Estimates (including SPH), and Wavelet Galerkin methods.

  • Belytschko, 1996 [17], provided a wide overview of methods ranging from SPH over MLS approaches to PU and Galerkin methods and GFDM. The methods are compared according to their main principles, and application examples are provided from solid mechanics.

  • Li & Liu, 2002 [138], gave an overview of meshfree and particle methods in general. This provided a cross-sectional view of particle methods with a focus on applications in structural mechanics. The same authors in 2004 then published a now-classic book on particle methods [137], particularly focusing on meshfree

Galerkin and PU methods. However, the book is much broader and also touches on molecular dynamics methods and multi-scale particle methods. It includes theory, algorithms, and application cases.

  • A reference book on meshfree methods was written by Liu & Karamanlidis, 2003 [145]. It contains an introduction to several weak and strong form methods with more in-depth derivations of mostly weak-form methods, such as D-EM, EFG, MLPG, SPH, Point Interpolation Method (PIM), and the Boundary-Point Interpolation Method (B-PIM). The second part of the book focuses on applications in solid (beams, plates, shells) and fluid (convection, hydrodynamics) mechanics.

  • An overview of meshfree Galerkin methods for PDEs was given by Fries & Matthies, 2004 [75]. This contained PU methods and Galerkin approximations with and without extrinsic basis. The paper particularly discussed the choice of test functions. Meshfree collocation methods were not discussed, albeit some mathematical formulations of meshfree finite difference methods can be found in the paper, for example for GMLS, and their relation to meshfree Galerkin methods is discussed.

  • Nguyen et al., 2008 [173], reviewed meshfree methods for solid mechanics problems. This mainly included weak-form methods, covering a wide spectrum of aspects ranging from their mathematical formulation to software implementations.

  • Liu, 2009 [144] provided a large compendium of meshfree methods. It discusses fundamental concepts of function and derivative approximation on scattered nodes and then delves into several families of methods, including SPH, RKPM, MLS, WLS, PIM, EFG, and MLPG. This provides a broad overview of both strong- and weak-form methods, and it also explores their application in solid and fluid mechanics and discusses their integration with other methods in hybrid and multi-scale simulations.

  • Chen, Hillman & Chi, 2017 [40] presented a comprehensive overview of meshfree approximation techniques. They juxtaposed different ways of obtaining meshfree approximations of a function, including approximations based on Least Squares (LS, WLS, MLS), KE, Reproducing Kernel Approximations (RKA), and PU methods. They categorize meshfree approximation of derivatives into five classes: Direct Derivatives, Diffuse Derivatives, Implicit Derivatives, Synchronized Derivatives, and Generalized Finite Differences. We will refer to this classification further down when discussing methods. Although many meshfree methods are listed, this article did not highlight differences and commonalities across methods.

  • Jacquemin et al., 2020 [101], gave an overview of strong-form meshfree collocation methods derived from Taylor expansions. It is an excellent tutorial article for accessing the field of meshfree methods, as it also provides several examples and benchmark problems to compare methods. For many methods, detailed step-by-step derivations are given. This includes DC-PSE, GFDM, RBF-FD, MLS, and IMLS. Finally, this article unifies DC-PSE and GFDM into a single formulation.

  • One of the most recent books on meshfree methods was authored by Belytschko, Chen & Hillman in 2024 [16]. This book focuses on meshfree Galerkin methods in MLS and RK formulations, which are introduced by considering problems from linear (diffusion, linear elasticity) and non-linear continuum mechanics. This book also follows the classification of derivative approximations given earlier by two of the authors [40], discussing methods using diffuse derivatives, implicit derivatives, synchronized derivatives, and direct derivatives. In this, the problem of quadrature is given particular attention, and various numerical integration methods are compared. Even though the book focuses on meshfree Galerkin methods, the comparison of nodally integrated meshfree Galerkin methods and nodally collocated meshfree methods also includes some material on meshfree collocation methods.

The remainder of this paper is structured as follows: We start in § 3 by providing a unifying mathematical formulation of meshfree collocation methods for strong-form PDE solution. This allows us to define the notation and review the approximation principles that are common to all meshfree collocation methods. In a small subsection, we also introduce a compact matrix notation for this formulation.

All methods reviewed here follow this general formulation. They are, however, derived differently. We therefore propose a classification of meshfree collocation methods w.r.t. their principle of derivation. This distinguishes methods derived by moment approximation (§ 4), methods derived by ℓ2\ell_2 minimization of the discretization error (§ 5), methods derived by ℓ2\ell_2 minimization of the stencil weights (Section 5), and methods derived by generalized ℓ2\ell_2 minimization (§ 7). In each of these sections, we provide the detailed derivation starting from the unifying definition of § 3, followed by a discussion of the methods that fall into the respective category. In this, we also mention further classifications of the methods, for example w.r.t. the type of derivative approximation [40], and we cite examples of applications.

Finally, in § 8, we summarize the reviewed methods. This in particular entails a table of all reviewed methods. In this table, the general formulation of each method is given in the notation of § 3, along with its classification according to the optimization principle and the type of derivative approximation.

The main text is followed by four Appendices. Appendix A recapitulates the general formulation from § 3 in component-wise notation in two dimensions. This serves to further clarify notation and provde a didactic example of what the methods look like when all terms are explicitly written out. Appendix B contains the formal derivation of the analytical solution for the ℓ2\ell_2 error minimization from § 5. Appendix C does the same for the ℓ2\ell_2 minimization problem over the weights from Section 5. Appendix D provides the formal solution for the generalized ℓ2\ell_2 minimization problem from § 7. Finally, the Supplementary Material provides all details of every method discussed, serving as a reference.

General formulation of meshfree collocation methods

All numerically consistent methods for approximating differential operators on scattered nodes follow a common scheme. In this scheme, the function approximation at any given point can be interpreted as an interpolation or convolution-like operation over the values at neighboring particles within a certain finite neighborhood, multiplied with suitable weights. In all consistent methods, the moments of the weight function must fulfill certain conditions. Different meshfree collocation methods mainly differ in how these conditions are enforced (e.g., by minimization, constrained minimization, or exactly), and what ansatz is used for the weight function. Different design choices lead to approximations with varying accuracy and stability properties.

We formulate the general definition of meshfree collocation methods for an open continuous domain Ω⊂Rn\Omega\subset\mathbb{R}^n containing a set of NN collocation points (nodes, particles) X:={x1,…,xN:xi∈Ω‾}\mathcal{X} := \{x_1,\ldots,x_N : x_i \in\overline{\Omega}\}, where Ω‾=Ω∪∂Ω\overline{\Omega} = \Omega\cup\partial\Omega, at locations xi:=(xi,1,…,xi,n)T=(xi,β)β=1nx_i := (x_{i,1},\ldots,x_{i,n})^\mathsf{T} = (x_{i,\beta})_{\beta=1}^{n}. Every point can be addressed by its index P:={i:xi∈X}\mathcal{P} := \{i : x_i \in\mathcal{X}\}.

Each particle i∈Pi \in\mathcal{P} is surrounded by neighboring particles Ni:={j∈P:∥xj−xi∥2<hi}\mathcal{N}_i := \{j \in\mathcal{P} : \lVert x_j-x_i\rVert_2 < h_i\} within a disk defined by the stencil radius hih_i, which is also sometimes called smoothing length, cut-off radius or interaction radius4. We similarly define neighboring particle sets Nx\mathcal{N}_x for any point x∈Ω‾x \in\overline{\Omega}, not necessarily coinciding with a particle location. Different particles ii can have different hih_i to allow for adaptive-resolution methods. Therefore, and because particle distributions can be non-uniform, different points ii generally have different numbers of neighbors Ni:=∣Ni∣N_i := \lvert\mathcal{N}_i\rvert. A characteristic length scale of the neighborhood can be defined for arbitrary node distributions as Δxi:=Vn(hi)/Nin\Delta x_i := \sqrt[n]{V_n(h_i)/N_i}, where Vn(r)V_n(r) is nn-dimensional volume of a Euclidean ball of radius rr.

Together with the stencil radius, this defines the resolution ratio hi/Δxih_i/\Delta x_i, allowing to estimate Ni≈Vn(hi/Δxi)N_i \approx V_n(h_i/\Delta x_i) for locally homogeneous point distributions.

References

  1. [19]A. K. Ghosh and S. M. Deshpande. Robust least squares kinetic upwind method for inviscid compressible flows. 1995.
  2. [20]B. Gross, N. Trask, P. Kuberry, and P. Atzberger. Meshfree methods on manifolds for hydrodynamic flows on curved surfaces: A generalized moving least-squares (gmls) approach. Journal of Computational Physics, 409:109340, 2020.DOI
  3. [21]M. Hillman, M. Pasetto, and G. Zhou. Generalized reproducing kernel peridynamics: unification of local and non-local meshfree methods, non-local derivative operations, and an arbitrary-order state-based peridynamic formulation. Computational Particle Mechanics, 7(2):435–469, Mar 2020.DOI
  4. [22]A. Huerta, T. Belytschko, S. Fernández-Méndez, and T. Rabczuk. Meshfree methods. 2004.
  5. [23]T. Jacquemin, S. Tomar, K. Agathos, S. Mohseni-Mofidi, and S. P. A. Bordas. Taylor-series expansion based numerical methods: A primer, performance benchmarking and new approaches for problems with non-smooth solutions. Archives of Computational Methods in Engineering, 27:1465–1513, 11 2020.DOI
  6. [24]P. S. Jensen. Finite difference techniques for variable grids. Computers & Structures, 2(1):17–29, 1972.DOI
  7. [25]G. Joldes, G. Bourantas, B. Zwick, H. Chowdhury, A. Wittek, S. Agrawal, K. Mountris, D. Hyde, S. K. Warfield, and K. Miller. Suite of meshless algorithms for accurate computation of soft tissue deformation for surgical simulation. Medical Image Analysis, 56:152–171, Aug. 2019.DOI
  8. [26]G. R. Joldes, H. A. Chowdhury, A. Wittek, B. Doyle, and K. Miller. Modified moving least squares with polynomial bases for scattered data approximation. Applied Mathematics and Computation, 266:893–902, Sept. 2015.DOI
  9. [27]D. W. Kim and Y. Kim. Point collocation method using the fast moving least-square reproducing kernel approximation. International Journal for Numerical Methods in Engineering, 56:1445 – 1464, 03 2003.DOI
  10. [28]J. King and S. Lind. High-order simulations of isothermal flows using the local anisotropic basis function method (labfm). Journal of Computational Physics, 449:110760, 1 2022.DOI
  11. [29]J. King, S. Lind, and A. Nasar. High order difference schemes using the local anisotropic basis function method. Journal of Computational Physics, 415:109549, 8 2020.DOI
  12. [30]G. Kosec, J. Slak, M. Depolli, R. Trobec, K. Pereira, S. Tomar, T. Jacquemin, S. P. Bordas, and M. Abdel Wahab. Weak and strong from meshless methods for linear elastic problem under fretting contact conditions. Tribology International, 138:392–402, 2019.DOI
  13. [31]J. Kuhnert and S. Tiwari. Finite pointset method based on the projection method for simulations of the incompressible navier-stokes equations. Technical Report 30, Fraunhofer (ITWM), 2001.
  14. [32]J. Kuhnert and S. Tiwari. Grid free method for solving the poisson equation. Technical Report 25, Fraunhofer (ITWM), 2001.DOI
  15. [33]P. Lancaster and K. Salkauskas. Surfaces generated by moving least squares methods. Mathematics of Computation, 37:141–158, 1981.DOI
  16. [34]S. K. Lele. Compact finite difference schemes with spectral-like resolution. Journal of Computational Physics, 103(1):16–42, Nov. 1992.DOI
  17. [35]D. Levin. The approximation power of moving least-squares. Math. Comput., 67:1517–1531, 1998.DOI

Paper details

vlnc:W_vqym3xj9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents