Particle method

{{Short description|Class of numerical methods in scientific computing}} {{Use American English|date = March 2019}} '''Particle methods''' is a widely used class of numerical algorithms in scientific computing. Its application ranges from computational fluid dynamics (CFD) over molecular dynamics (MD) to discrete element methods.

==History==

One of the earliest particle methods is smoothed particle hydrodynamics, presented in 1977.<ref>Gingold RA, Monaghan JJ (1977). Smoothed particle hydrodynamics – theory and application to non-spherical stars. Mon Not R Astron Soc 181:375–389</ref> Libersky ''et al.''<ref>Libersky, L.D., Petscheck, A.G., Carney, T.C., Hipp, J.R., Allahdadi, F.A. (1993). High Strain Lagrangian Hydrodynamics. ''Journal of Computational Physics''.</ref> were the first to apply SPH in solid mechanics. The main drawbacks of SPH are inaccurate results near boundaries and tension instability that was first investigated by Swegle.<ref>Swegle, J.W., Hicks, D.L., Attaway, S.W. (1995). Smoothed Particle Hydrodynamics Stability Analysis. ''Journal of Computational Physics''. 116(1), 123-134</ref>

In the 1990s a new class of particle methods emerged. The reproducing kernel particle method<ref>Liu, W.K., Jun, S., Zhang, Y.F. (1995), Reproducing kernel particle methods, ''International Journal of Numerical Methods in Fluids''. 20, 1081-1106. </ref> (RKPM) emerged, the approximation motivated in part to correct the kernel estimate in SPH: to give accuracy near boundaries, in non-uniform discretizations, and higher-order accuracy in general. Notably, in a parallel development, the Material point methods were developed around the same time<ref>D. Sulsky, Z., Chen, H. Schreyer (1994). a Particle Method for History-Dependent Materials. ''Computer Methods in Applied Mechanics and Engineering'' (118) 1, 179-196.</ref> which offer similar capabilities. During the 1990s and thereafter several other varieties were developed including those listed below.

==List of methods and acronyms==

The following numerical methods are generally considered to fall within the general class of "particle" methods. Acronyms are provided in parentheses.

* Smoothed particle hydrodynamics (SPH) (1977) * Dissipative particle dynamics (DPD) (1992) * Reproducing kernel particle method (RKPM) (1995) * Moving particle semi-implicit (MPS) * Particle-in-cell (PIC) * Moving particle finite element method (MPFEM) * Cracking particles method (CPM) (2004) * Immersed particle method (IPM) (2006)

==Definition==

The mathematical definition of particle methods captures the structural commonalities of all particle methods.<ref name="pahlke">{{cite journal |last1=Pahlke |first1=Johannes |last2=Sbalzarini |first2=Ivo F. |title=A Unifying Mathematical Definition of Particle Methods |journal=IEEE Open Journal of the Computer Society |date=March 2023 |volume=4 |pages=97–108 |doi=10.1109/OJCS.2023.3254466|s2cid=257480034 |doi-access=free }} {{CC-notice|cc=by4}}</ref> It, therefore, allows for formal reasoning across application domains. The definition is structured into three parts: First, the particle method algorithm structure, including structural components, namely data structures, and functions. Second, the definition of a particle method instance. A particle method instance describes a specific problem or setting, which can be solved or simulated using the particle method algorithm. Third, the definition of the particle state transition function. The state transition function describes how a particle method proceeds from the instance to the final state using the data structures and functions from the particle method algorithm.<ref name="pahlke" />

A '''particle method algorithm''' is a 7-tuple <math>(P, G, u, f, i, e, \overset{\circ}{e})</math>, consisting of the two data structures <math> \begin{align} &P := A_1 \times A_2 \times ... \times A_n &&\text{the particle space,}\\ &G := B_1 \times B_2 \times ... \times B_m &&\text{the global variable space,} \end{align} </math>

such that <math>[G\times P^*]</math> is the state space of the particle method, and five functions: <math> \begin{align} &u: [G \times P^*] \times \mathbb N \rightarrow \mathbb N^* &&\text{the neighborhood function,}\\ &f: G \rightarrow \{ \top,\bot \} &&\text{the stopping condition,}\\ &i: G \times P \times P \rightarrow P\times P &&\text{the interact function,}\\ &e: G \times P\rightarrow G \times P^* \ &&\text{the evolve function,} \\ &\overset{\circ}{e} : G \rightarrow G &&\text{the evolve function of the global variable.} \end{align} </math>

An initial state defines a '''particle method instance''' for a given particle method algorithm <math>(P, G, u, f, i, e, \overset{\circ}{e})</math>:

<math> [g^1,\mathbf{p}^1] \in [G\times P^*]. </math>

The instance consists of an initial value for the global variable <math>g^1 \in G</math> and an initial tuple of particles <math>\mathbf p^1 \in P^*</math>.

In a specific particle method, the elements of the tuple <math>(P, G, u, f, i, e, \overset{\circ}{e})</math> need to be specified. Given a specific starting point defined by an instance <math>[g^{1},\mathbf{p}^{1}]</math>, the algorithm proceeds in iterations. Each iteration corresponds to one state transition step <math>s</math> that advances the current state of the particle method <math>[g^{t},\mathbf{p}^{t}]</math> to the next state <math>[g^{t+1},\mathbf{p}^{t+1}]</math>. The state transition uses the functions <math>u, i, e, \overset{\circ}{e}</math> to determine the next state. The '''state transition function''' <math>S</math> generates a series of state transition steps until the stopping function <math>f</math> is <math>true</math>. The so-calculated final state is the result of the state transition function. The state transition function is identical for every particle method.

The '''state transition function''' is defined as

<math> S : [G\times P^*] \rightarrow [G\times P^*] </math>

with

<math> [g^T, \mathbf p^T]:=S([g^1, \mathbf p^1]) </math>.

The pseudo-code illustrates the particle method state transition function:

1 <math>[g, \mathbf p] = [g^1, \mathbf p^1]</math> 2 '''while''' <math>f(g)=false</math> 3 '''for''' <math>j = 1</math> '''to''' <math>|\mathbf p|</math> 4 <math>\mathbf k=u([g,\mathbf p],j)</math> 5 '''for''' <math>l = 1</math> '''to''' <math>|\mathbf k|</math> 6 <math>(p_j,p_{k_j})=i(g,p_j,p_{k_j})</math> 7 <math>\mathbf q = ()</math> 8 '''for''' <math>j = 1</math> '''to''' <math>|\mathbf p|</math> 9 <math>(g,\overline{\mathbf q})=e(g,p_j)</math> 10 <math>\mathbf q=\mathbf q\circ\overline{\mathbf q}</math> 11 <math>\mathbf p=\mathbf q</math> 12 <math>g=\overset{\circ}{e}(g)</math> 13 <math>[g^T, \mathbf p^T] = [g, \mathbf p]</math>

The fat symbols are tuples, <math>\mathbf p, \mathbf q</math> are particle tuples and <math> \mathbf k</math> is an index tuple. <math> ()</math> is the empty tuple. The operator <math>\circ</math> is the concatenation of the particle tuples, e.g. <math>(p_1,p_2)\circ(p_3,p_4,p_5)=(p_1,p_2,p_3,p_4,p_5)</math>. And <math> |\mathbf p|</math> is the number of elements in the tuple <math> \mathbf p</math>, e.g. <math>|(p_1,p_2)|=2</math>.

==References== {{reflist}}

==Further reading== {{refbegin}} * Liu MB, Liu GR, Zong Z, AN OVERVIEW ON SMOOTHED PARTICLE HYDRODYNAMICS, INTERNATIONAL JOURNAL OF COMPUTATIONAL METHODS Vol. 5 Issue: 1, 135–188, 2008. * Liu, G.R., Liu, M.B. (2003). ''Smoothed Particle Hydrodynamics, a meshfree and Particle Method'', World Scientific, {{ISBN|981-238-456-1}}. {{refend}}

==External links== * [https://www.particleworks.com/technical_column01_en.html Particle Methods]

{{DEFAULTSORT:Particle Method}} Category:Numerical analysis Category:Numerical differential equations Category:Computational fluid dynamics