Particle method

From Quire, the open reference·Class of numerical methods in scientific computing·4 min read

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#edit

One of the earliest particle methods is smoothed particle hydrodynamics, presented in 1977.^[1] Libersky et al.^[2] 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.^[3]

In the 1990s a new class of particle methods emerged. The reproducing kernel particle method^[4] (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^[5] which offer similar capabilities. During the 1990s and thereafter several other varieties were developed including those listed below.

List of methods and acronyms#edit

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#edit

The mathematical definition of particle methods captures the structural commonalities of all particle methods.^[6] 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.^[6]

A particle method algorithm is a 7-tuple ${\displaystyle (P,G,u,f,i,e,{\overset {\circ }{e)}$ , consisting of the two data structures ${\displaystyle {\begin{aligned}&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{$

such that ${\displaystyle [G\times P^{*}]}$ is the state space of the particle method, and five functions: ${\displaystyle {\begin{aligned}&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$

An initial state defines a particle method instance for a given particle method algorithm ${\displaystyle (P,G,u,f,i,e,{\overset {\circ }{e)}$ :

{{mathimg|3d39e87b8e60e5bf0b4859702100207dce0005e7|width=19.364ex|height=3.176ex|va=-0.838ex|alt={\displaystyle [g^{1},\mathbf {p} ^{1}]\in [G\times P^{*}].}}}

The instance consists of an initial value for the global variable ${\displaystyle g^{1}\in G}$ and an initial tuple of particles ${\displaystyle \mathbf {p} ^{1}\in P^{*$ .

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

{{mathimg|d7c8d502c913649a49cde52447d50e3ed5f02def|width=24.724ex|height=2.843ex|va=-0.838ex|alt={\displaystyle S:[G\times P^{*}]\rightarrow [G\times P^{*}]}}}

with

{{mathimg|b4b862268056ae291166d6d0a485a79c9e41edeb|width=21.803ex|height=3.176ex|va=-0.838ex|alt={\displaystyle [g^{T},\mathbf {p} ^{T}]:=S([g^{1},\mathbf {p} ^{1}])}}}.

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

 1 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mo stretchy="false">[</mo>
        <mi>g</mi>
        <mo>,</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mo stretchy="false">]</mo>
        <mo>=</mo>
        <mo stretchy="false">[</mo>
        <msup>
          <mi>g</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>1</mn>
          </mrow>
        </msup>
        <mo>,</mo>
        <msup>
          <mrow class="MJX-TeXAtom-ORD">
            <mi mathvariant="bold">p</mi>
          </mrow>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>1</mn>
          </mrow>
        </msup>
        <mo stretchy="false">]</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle [g,\mathbf {p} ]=[g^{1},\mathbf {p} ^{1}]}</annotation>
  </semantics>

 2 while 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>f</mi>
        <mo stretchy="false">(</mo>
        <mi>g</mi>
        <mo stretchy="false">)</mo>
        <mo>=</mo>
        <mi>f</mi>
        <mi>a</mi>
        <mi>l</mi>
        <mi>s</mi>
        <mi>e</mi>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle f(g)=false}</annotation>
  </semantics>

 3   for 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>j</mi>
        <mo>=</mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle j=1}</annotation>
  </semantics>
 to 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle |\mathbf {p} |}</annotation>
  </semantics>

 4     
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">k</mi>
        </mrow>
        <mo>=</mo>
        <mi>u</mi>
        <mo stretchy="false">(</mo>
        <mo stretchy="false">[</mo>
        <mi>g</mi>
        <mo>,</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mo stretchy="false">]</mo>
        <mo>,</mo>
        <mi>j</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \mathbf {k} =u([g,\mathbf {p} ],j)}</annotation>
  </semantics>

 5     for 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>l</mi>
        <mo>=</mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle l=1}</annotation>
  </semantics>
 to 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">k</mi>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle |\mathbf {k} |}</annotation>
  </semantics>

 6       
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mo stretchy="false">(</mo>
        <msub>
          <mi>p</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>j</mi>
          </mrow>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>p</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <msub>
              <mi>k</mi>
              <mrow class="MJX-TeXAtom-ORD">
                <mi>j</mi>
              </mrow>
            </msub>
          </mrow>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>=</mo>
        <mi>i</mi>
        <mo stretchy="false">(</mo>
        <mi>g</mi>
        <mo>,</mo>
        <msub>
          <mi>p</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>j</mi>
          </mrow>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>p</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <msub>
              <mi>k</mi>
              <mrow class="MJX-TeXAtom-ORD">
                <mi>j</mi>
              </mrow>
            </msub>
          </mrow>
        </msub>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle (p_{j},p_{k_{j}})=i(g,p_{j},p_{k_{j}})}</annotation>
  </semantics>

 7   
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">q</mi>
        </mrow>
        <mo>=</mo>
        <mo stretchy="false">(</mo>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \mathbf {q} =()}</annotation>
  </semantics>

 8   for 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>j</mi>
        <mo>=</mo>
        <mn>1</mn>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle j=1}</annotation>
  </semantics>
 to 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mrow class="MJX-TeXAtom-ORD">
          <mo stretchy="false">|</mo>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle |\mathbf {p} |}</annotation>
  </semantics>

 9     
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mo stretchy="false">(</mo>
        <mi>g</mi>
        <mo>,</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mover>
            <mrow class="MJX-TeXAtom-ORD">
              <mi mathvariant="bold">q</mi>
            </mrow>
            <mo accent="false">¯</mo>
          </mover>
        </mrow>
        <mo stretchy="false">)</mo>
        <mo>=</mo>
        <mi>e</mi>
        <mo stretchy="false">(</mo>
        <mi>g</mi>
        <mo>,</mo>
        <msub>
          <mi>p</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>j</mi>
          </mrow>
        </msub>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle (g,{\overline {\mathbf {q} }})=e(g,p_{j})}</annotation>
  </semantics>

10     
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">q</mi>
        </mrow>
        <mo>=</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">q</mi>
        </mrow>
        <mo>∘</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mover>
            <mrow class="MJX-TeXAtom-ORD">
              <mi mathvariant="bold">q</mi>
            </mrow>
            <mo accent="false">¯</mo>
          </mover>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \mathbf {q} =\mathbf {q} \circ {\overline {\mathbf {q} }}}</annotation>
  </semantics>

11   
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mo>=</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">q</mi>
        </mrow>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle \mathbf {p} =\mathbf {q} }</annotation>
  </semantics>

12   
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mi>g</mi>
        <mo>=</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mover>
            <mi>e</mi>
            <mo>∘</mo>
          </mover>
        </mrow>
        <mo stretchy="false">(</mo>
        <mi>g</mi>
        <mo stretchy="false">)</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle g={\overset {\circ }{e}}(g)}</annotation>
  </semantics>

13 
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <mo stretchy="false">[</mo>
        <msup>
          <mi>g</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>T</mi>
          </mrow>
        </msup>
        <mo>,</mo>
        <msup>
          <mrow class="MJX-TeXAtom-ORD">
            <mi mathvariant="bold">p</mi>
          </mrow>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>T</mi>
          </mrow>
        </msup>
        <mo stretchy="false">]</mo>
        <mo>=</mo>
        <mo stretchy="false">[</mo>
        <mi>g</mi>
        <mo>,</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi mathvariant="bold">p</mi>
        </mrow>
        <mo stretchy="false">]</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle [g^{T},\mathbf {p} ^{T}]=[g,\mathbf {p} ]}</annotation>
  </semantics>

The fat symbols are tuples, ${\displaystyle \mathbf {p} ,\mathbf {q} }$ are particle tuples and ${\displaystyle \mathbf {k} }$ is an index tuple. ${\displaystyle ()}$ is the empty tuple. The operator ${\displaystyle \circ }$ is the concatenation of the particle tuples, e.g. ${\displaystyle (p_{1},p_{2})\circ (p_{3},p_{4},p_{5})=(p_{1},p_{2},p_{3},p_{4},p_{5})}$ . And ${\displaystyle |\mathbf {p} |}$ is the number of elements in the tuple ${\displaystyle \mathbf {p} }$ , e.g. ${\displaystyle |(p_{1},p_{2})|=2}$ .

References#edit

^ Gingold RA, Monaghan JJ (1977). Smoothed particle hydrodynamics – theory and application to non-spherical stars. Mon Not R Astron Soc 181:375–389
^ Libersky, L.D., Petscheck, A.G., Carney, T.C., Hipp, J.R., Allahdadi, F.A. (1993). High Strain Lagrangian Hydrodynamics. Journal of Computational Physics.
^ Swegle, J.W., Hicks, D.L., Attaway, S.W. (1995). Smoothed Particle Hydrodynamics Stability Analysis. Journal of Computational Physics. 116(1), 123-134
^ Liu, W.K., Jun, S., Zhang, Y.F. (1995), Reproducing kernel particle methods, International Journal of Numerical Methods in Fluids. 20, 1081-1106.
^ 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.
^ a b Pahlke, Johannes; Sbalzarini, Ivo F. (March 2023). "A Unifying Mathematical Definition of Particle Methods". IEEE Open Journal of the Computer Society. 4: 97–108. doi:10.1109/OJCS.2023.3254466. S2CID 257480034. This article incorporates text available under the CC BY 4.0 license.

External links#edit

Particle Methods

This article is mirrored from “Particle method” on English Wikipedia, revision 1212528485, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1212528485 · just now