2.1 Equations to be solved
The fluid flow is modeled by three conservation equations, which describe the relation between the velocity
\(\mathbf {v} = (u, v, w)^T\), the pressure
p, and the temperature
T. Let
$$\begin{aligned} \frac{d}{dt} = \frac{\partial }{\partial t} + \mathbf {v}^T \cdot \nabla \end{aligned}$$
(1)
denote the material derivative, which models the change of a physical property along the trajectory of a fluid particle. As the material derivative is “naturally” represented by FPM’s discretization technique, we will employ this operator wherever a time derivative is involved. For the scope of this paper, we restrict ourselves to the case of incompressible fluids. In particular, we have constant density along the path of a fluid particle
\((\frac{d}{dt} \rho = 0)\).
The three conservation equations are:
-
The conservation of momentum, which is given by
$$\begin{aligned} \frac{d}{dt} \left( \rho \mathbf {v} \right) = \left( \nabla ^T S \right) ^T - \nabla p + \rho g \end{aligned}$$
(2)
where
\(\rho \) denotes the density,
S is the stress tensor (see below), and
g contains the external body forces.
-
The conservation of mass, which is enforced by the continuity equation
$$\begin{aligned} \nabla ^T \cdot \rho \mathbf {v} = 0 \end{aligned}$$
(3)
-
The conservation of energy, which is controlled by the temperature equation
$$\begin{aligned} \begin{aligned} ( \rho c_V ) \frac{d}{dt} T ={}&\nabla ^T ( S \cdot \mathbf {v} )- ( \nabla ^T S ) \cdot \mathbf {v} \\&- p (\nabla ^T \mathbf {v}) + \nabla ^T ( k \nabla T ) + q \end{aligned} \end{aligned}$$
(4)
where
T denotes the temperature,
k the heat conductivity, and
\(c_v\) the heat capacity.
Within the scope of this paper, we limit ourselves to the case of viscous stress tensors,
$$\begin{aligned} S = S_{\text {visc}} = \eta \frac{d \epsilon }{dt}, \end{aligned}$$
(5)
where
\(\eta \) denotes the viscosity of the fluid, and
$$\begin{aligned} \frac{d \epsilon }{dt} = \frac{1}{2} \left[ \nabla \left( \mathbf {v} \right) ^T + \left( \nabla \left( \mathbf {v} \right) ^T \right) ^T \right] - \frac{1}{3} \left[ \nabla ^T \mathbf {v} \right] I. \end{aligned}$$
(6)
is the strain rate tensor. Equation (
2) hence can be re-written as
$$\begin{aligned} \frac{d}{dt} \left( \rho \mathbf {v} \right) = \left( \nabla ^T \eta \frac{d \epsilon }{dt} \right) ^T - \nabla p + \rho g \end{aligned}$$
(7)
Before we turn ourselves to the discretized counterparts of the Eqs. (
2) and (
3), we first describe the FPM discretization technique.
2.2 Organization of the point cloud
For each phase (water, air, oil, etc.) a separate point cloud \(\mathcal {P} = \left\{ \mathbf {x_i} \right\} \) is defined. The density of the point cloud is determined by the smoothing length \(h = h(\mathbf {x}, t)\), which can be given as a function of space and time (but is constant per phase in most applications). Via this parameter, the resolution of the discretized problems is steered.
In order to discretize the differential operators, the computational domain needs to be covered by balls of radius
\(r_{\text {hole}} \cdot h\) around each point. However, points may not be too close to each other, i.e. they have to keep a minimum distance of
\(r_{\text {min}} \cdot h\). Typical values of
\(r_{\text {hole}}=0.45\) and
\(r_{\text {min}} \in [0.1,0.2]\). This leads to a point cloud where between 20 and 50 points can be found within each ball of radius
h (independent of
h). The boundaries of the domain are also filled with points, see Sect.
2.5.
2.3 Construction of differential operators
The differential operators are discretized using generalized finite differences defined via the points
\(\mathbf {x}_i\),
\(i=1,\ldots ,N\) of the cloud. The method is very similar to the Moving Least Squares method (MLS) by Lancaster and Salkauskas [
8]. For each physical quantity
f, we identify its value at the point
\(\mathbf {x}_i\),
$$\begin{aligned} f_i = f (\mathbf {x}_i) \end{aligned}$$
(8)
and let the derivatives be approximated by sums of the form
$$\begin{aligned} \partial ^{*} f = \sum _{j \in N_i} c_{ij}^{*} f_j \end{aligned}$$
(9)
where
\(*\) denotes the desired derivative, e.g.
\(*=0\) (function evaluation),
\(*=x\) (first derivative in
x-direction),
\(*=\varDelta \) (Laplacian).
\(N_i\) is the neighborhood of point
\(\mathbf {x}_i\) consisting of the nearest points
\(\mathbf {x}_j\) within a ball of radius
h around
\(\mathbf {x}_i\). The set
\(N_i\) must be large enough such that all derivatives needed for the PDE’s discretization can be set up, we usually have
\(\vert N_i \vert = 40\) for second order PDEs. Note that the relation
\(j \in N_i\) is not symmetric.
The coefficients \(c^{*}_{ij}\) need to be independent of f to avoid expensive computations, thus, we compute them such that they exactly reproduce the considered differential operator for monomials up to a certain (typically: second) order.
We therefore define, for each point
\(\mathbf {x}_i\), a set of
M discrete test vectors
\( \left( k^m_i \right) _{m=1}^M\), where each
\(k^m_i = \left( k^m_{i,j} \right) _{j \in N_i}\) represents the discretization of a test function (monomial) within the neighborhood
\(N_i\), while
\(b_{i,m}^{*}\) contains the value of its derivative
\(*\) at the point
\(\mathbf {x}_i\). In this terms, the requirements of exact differentiation for the test functions translates to
$$\begin{aligned} \sum _{j \in N_i} k_{i,j}^m c_{ij}^{*} = b_{i,m}^{*} \quad \text{ for } \text{ all } m=1,\ldots ,M, \end{aligned}$$
(10)
or, in matrix form,
$$\begin{aligned} K_i^T c^{*}_i = b_i^{*}, \end{aligned}$$
(11)
where the
m-th row of
\(K^T_i\) consists of the entries
\(\left( k^m_{i,j} \right) _{j \in N_i}\), and the vectors
\(b_i^{*}\) and
\(c^{*}_i\) are given by
\(b_i^{*} = \left( b_{i,m}^{*} \right) _{m=1}^M\) and
\(c^{*}_i = \left( c_{ij}^{*} \right) _{j \in N_i}\). Furthermore, the distance of the points should be taken into account. To this end, we introduce a weight function,
$$\begin{aligned} w(r_{i,j}) = {\left\{ \begin{array}{ll} \exp (-4 \cdot r^2) - \exp (-4), &{} \quad \text{ if } \ r_{i,j} < 1\\ 0, &{}\quad \text{ otherwise } \end{array}\right. } \end{aligned}$$
(12)
where the distance function
\(r_{i,j}\) is given by
$$\begin{aligned} r_{i,j} = r (\mathbf {x}_i, \mathbf {x}_j ) = 2 \frac{\Vert \mathbf {x}_i - \mathbf {x}_j \Vert }{h (\mathbf {x}_i) + h ( \mathbf {x}_j)}. \end{aligned}$$
(13)
We group, for each
i, the weights into a diagonal matrix
$$\begin{aligned} W_i = \begin{pmatrix} w_{i,1} &{} \quad &{} \quad &{} \\ &{} \quad w_{i,2} &{} \quad &{} \\ &{} \quad &{} \quad \ddots &{}\\ &{} \quad &{} \quad &{} \quad w_{i,\vert N_i \vert } \end{pmatrix}, \end{aligned}$$
(14)
where
\(w_{i,j} = w(r_{i,j}) = w(r(\mathbf {x}_i,\mathbf {x}_j))\). With the aid of the matrices
\(K_i\) and
\(W_i\), we formulate the conditions for
\(c_i^{*}\) in a least-squares sense, i.e.
$$\begin{aligned}&\frac{1}{2} \left( c_i^{*} \right) ^T W_i^{-2} c_i^{*} \rightarrow \min \end{aligned}$$
(15)
$$\begin{aligned}&K_i^T c_i^{*} = b_i^{*}. \end{aligned}$$
(16)
We solve these small least-squares systems for each point
\(\mathbf {x}_i\) directly and construct the discretized differential operator (
9).
Note that at the boundary we can use the same ideas as in the interior of the domain: For Dirichlet boundaries, we set the central stencil value
\(c_{ii} ^\text {D} = 1\) and the other stencil values to 0. For Neumann boundary conditions, we need to compute the normal based on the neighbors that are also boundary points and then solve a least squares problem in order to find a discretization of the normal derivative. See [
17] for more details on boundary conditions.
2.4 FPM discretization of the conservation laws
In this section, we describe the implicit Euler time stepping scheme used to solve the partial differential equations introduced in Sect.
2.1. We present two different methods: First, the
segregated approach, where the velocity is computed using a Chorin projection-like ansatz, and the
coupled approach, where a divergence-free velocity field is computed directly by the solution of a saddle point system.
The finite pointset method employs a Lagrangian approach, i.e. the points move with the velocity field
\(\mathbf {v}\). This allows us to approximate material derivative of the velocity at the
i-th point by
$$\begin{aligned} \frac{d}{dt} \mathbf {v} (\mathbf {x}_i) \approx \frac{\mathbf {v}^{n+1} (\mathbf {x}^{n+1}_i) - \mathbf {v}^n (\mathbf {x}^n_i) }{\varDelta t}, \end{aligned}$$
(17)
where the superscript
n is used to indicate a quantity at a specific time step
n.
We integrate the momentum equation (
7) for each particle
\(\mathbf {x}_i\) and obtain
$$\begin{aligned} \begin{aligned}&\frac{\mathbf {v}^{n+1} (\mathbf {x}^{n+1}_i) - \mathbf {v}^n (\mathbf {x}^n_i)}{\varDelta t} = \frac{1}{\rho } \left[ \nabla ^T \left( \eta \frac{d\epsilon }{dt}\big \vert _{n+1} \right) \right] ^T \\&\qquad - \frac{1}{\rho } \nabla p^{n+1} (\mathbf {x}^{n+1}_i) + g^{n+1} (\mathbf {x}^{n+1}_i), \end{aligned} \end{aligned}$$
(18)
where
\(\frac{d\epsilon }{dt}\big \vert _{n+1}\) denotes the evaluation of the strain rate tensor at time step
\(n+1\). In the following, we omit the point coordinates
\((\mathbf {x}^n_i)\).
From (
6), we know that
\(\frac{d\epsilon }{dt}\) only depends on
\(\mathbf {v}\) and its derivatives, hence we define
$$\begin{aligned} \varPsi _{\eta } (\mathbf {v}) = \left( \nabla ^T ( \eta \frac{d\epsilon }{dt}) \right) ^T. \end{aligned}$$
(19)
(For example, for incompressible flow with constant viscosity, we have
\(\varPsi _{\eta } (\mathbf {v}) = \nabla ^T \left( \eta \nabla \mathbf {v} \right) \).)
We now re-organize (
18) such that all terms referring to time step
\(n+1\) move to the left hand side, while the terms depending on time step
n are on the right hand side. At this point, in the segregated approach we need to replace
\(p^{n+1}\) by an intermediate pressure
\(\hat{p}\). In consequence, we only solve for a velocity predictor
\(\hat{\mathbf {v}}^{n+1}\) here,
$$\begin{aligned} \left( I - \frac{\varDelta t}{\rho } \varPsi _{\eta } \right) (\hat{\mathbf {v}}^{n+1}) = \mathbf {v}^n - \frac{\varDelta t}{\rho } \nabla \hat{p} + \varDelta t \cdot g^{n+1}. \end{aligned}$$
(20)
The spatial discretization of this equation yields a sparse linear system of equations
\(\mathbf {A} \hat{\mathbf {v}}^{n+1}_h = \mathbf {f}_h\). The velocity solution
\(\hat{\mathbf {v}}^{n+1}\) of (
20) does not yet satisfy the continuity equation for incompressible fluids,
$$\begin{aligned} \nabla ^T \cdot \mathbf {v} = 0, \end{aligned}$$
(21)
and also does not take into account the pressure at the new time step
\(p^{n+1}\).
To this end, let us reconsider (
20) and replace
\(\hat{p}\) by the corrected pressure
\(p^{n+1} = \hat{p} + p_{\text {corr}}\) as well as the predicted velocity
\(\hat{\mathbf {v}}\) by the corrected velocity
\(v^{n+1}\),
$$\begin{aligned} \left( I - \frac{\varDelta t}{\rho } \varPsi _{\eta } \right) (\mathbf {v}^{n+1}) = \mathbf {v}^n - \frac{\varDelta t}{\rho } \nabla \hat{p} - \frac{\varDelta t}{\rho } \nabla p^{n+1}_{\text {corr}} + \varDelta t \cdot g^{n+1}. \end{aligned}$$
(22)
Subtracting (
20) from (
22) and taking the divergence yields
$$\begin{aligned} \begin{aligned}&\nabla ^T \cdot \mathbf {v}^{n+1} - \nabla ^T \cdot \hat{\mathbf {v}}^{n+1} \\&\quad - \nabla ^T \left[ \frac{\varDelta t}{\rho }\nabla \varPsi _{\eta } ( \mathbf {v}^{n+1} - \hat{\mathbf {v}}^{n+1} ) \right] {}= - \nabla ^T \left( \frac{\varDelta t}{\rho } \nabla p_{\text {corr}}^{n+1} \right) . \end{aligned} \end{aligned}$$
(23)
We assume that we can neglect the viscous term
$$\begin{aligned} \nabla ^T \left[ \frac{\varDelta t}{\rho }\nabla \varPsi _{\eta } ( \mathbf {v}^{n+1} - \hat{\mathbf {v}}^{n+1} ) \right] \end{aligned}$$
if the time step is small enough. In addition, for incompressible flow we require
\(\nabla ^T \mathbf {v}^{n+1} = 0\). It remains to solve the Poisson equation
$$\begin{aligned} \nabla ^T \left( \frac{\varDelta t}{\rho } \nabla p_{\text {corr}}^{n+1} \right) = (\nabla ^T \hat{\mathbf {v}}^{n+1} ), \end{aligned}$$
(24)
and use the gradient of the pressure correction
\(p_{\text {corr}}^{n+1}\) to update the velocity field.
A drawback of the segregated approach is the lack of accuracy in the case of low Reynolds numbers, i.e. when the magnitude of the term
\(\varPsi _{\eta } ( \mathbf {v}^{n+1} - \hat{\mathbf {v}}^{n+1} )\) would require time steps that are too small to allow for an effective simulation, see e.g. [
18] and the references therein for a detailed discussion. An option to overcome this problem is to solve for velocity and correction pressure in one single linear solve (
coupled approach). The correction pressure then serves as a Lagrangian multiplier, i.e. we solve the saddle point system
$$\begin{aligned}&\left( I - \frac{\varDelta t}{\rho } \varPsi _{\eta } \right) \left( \hat{\mathbf {v}}^{n+1} \right) + \frac{\varDelta t}{\rho } \nabla p_{\text {corr}}^{n+1} \nonumber \\&\quad = \mathbf {v}^n - \frac{\varDelta t}{\rho } \nabla \hat{p} + \varDelta t \cdot g^{n+1} \end{aligned}$$
(25)
$$\begin{aligned}&(\nabla ^T \hat{\mathbf {v}}^{n+1} ) - \nabla ^T \left( \frac{\varDelta t_{\text {virt}}}{\rho } \nabla p_{\text {corr}}^{n+1} \right) = 0, \end{aligned}$$
(26)
or, in matrix form,
$$\begin{aligned} \begin{pmatrix} \mathbf {A}_h &{} B_h \\ C_h &{} - D_h \end{pmatrix} \begin{pmatrix} {\hat{\mathbf {v}}}_h \\ p_h \end{pmatrix} = \begin{pmatrix} \mathbf {g}_h \\ f_h \end{pmatrix} \end{aligned}$$
(27)
The virtual time step
\(\varDelta t_{\text {virt}}\) is chosen as a fraction of the time step
\(\varDelta t\). Theoretically, the best possible value is
\(\varDelta t_{\text {virt}} = 0\), but smaller values make the linear system harder to solve.
While the coupled approach is more generally applicable than the segregated approach, it also takes more computational efforts. In Sect.
4.2 we give an example where the segregated approach fails, while the coupled approach produces a valid solution.
Regardless whether approach is used, we need an intermediate pressure
\(\hat{p}\). To this end, we take the divergence of the momentum equation (
2),
$$\begin{aligned} \begin{aligned} \nabla ^T \left( \frac{1}{\rho } \nabla p^{n+1} \right) ={}&- \nabla ^T \left( \frac{d}{dt} \mathbf {v}^{n+1} \right) \\&+\nabla ^T \left( g^{n+1} + \frac{1}{\rho } ( \nabla ^T S^{n+1} )^T \right) . \end{aligned} \end{aligned}$$
(28)
and split the pressure into two parts
\(p^{n+1} = p^{n+1}_{\text {hyd}} + p^{n+1}_{\text {dyn}}\). First, we formulate the equation for the
hydrostatic pressure
\(p^{n+1}_{\text {hyd}}\),
$$\begin{aligned} \nabla ^T \left( \frac{1}{\rho } \nabla p_{\text {hyd}}^{n+1} \right) = \nabla ^T g^{n+1} \end{aligned}$$
(29)
which can be computed without knowing the new velocity
\(\mathbf {v}^{n+1}\). In contrast, to update the dynamic pressure via
$$\begin{aligned} \begin{aligned} \nabla ^T \left( \frac{1}{\rho } \nabla p_{\text {dyn}}^{n+1} \right) ={}&- \nabla ^T \left( \frac{d}{dt} \nabla \mathbf {v}^{n+1} \right) \\&+ \nabla ^T \left( \frac{1}{\rho } ( \nabla ^T S^{n+1} )^T \right) = \nabla ^T \tilde{g}^{n+1}, \end{aligned} \end{aligned}$$
(30)
the updated velocity
\(\mathbf {v}^{n+1}\) is needed. Hence, in (
20) we use
\(\hat{p} = p_{\text {hyd}}^{n+1} + p_{\text {dyn}}^n\), i.e. we use the dynamic pressure from the previous time step and the hydrostatic pressure of the current time step.
The discrete form of (
29), (
30) and (
24) lead to scalar linear systems of the form
\(D p_h = f_h\). If the same boundary conditions are enforced, the matrices are equal within a time step.
Finally, the new temperature
\(T^{n+1}\) needs to be determined. As for velocity and pressure, we use an implicit scheme,
$$\begin{aligned} \begin{aligned}&(\rho c_V ) \cdot T^{n+1} - \varDelta t \cdot \left( k \cdot \nabla T^{n+1} \right) \\&\quad = (\rho C_V ) \cdot T^n\\&\qquad + \varDelta t \left( \nabla ^T ( S^{n+1} \cdot \mathbf {v}^{n+1} ) - ( \nabla ^T S^{n+1} ) \cdot \mathbf {v}^{n+1}\right) \\&\qquad - \varDelta t \left( p^{n+1} (\nabla ^T \mathbf {v}^{n+1}) + q \right) = \hat{q}. \end{aligned} \end{aligned}$$
(31)
The right hand side
\(\hat{q}\) only depends on quantities known at this stage. For the left hand side, we introduce
\(I_T - \varTheta _T = (\rho c_V ) - \varDelta t \nabla ^T \cdot ( k \nabla )\) and obtain the heat equation
$$\begin{aligned} \left( I_T - \varTheta _T \right) T^{n+1} = \hat{q}. \end{aligned}$$
(32)
To conclude this section, we recapitulate the equations we need to solve in every time step,
1.
Compute the hydrostatic pressure
\(p^{n+1}_{\text {hyd}}\) according to (
29),
2.
Set
\(\hat{p} = p^{n+1}_{\text {hyd}} + p^{n}_{\text {dyn}}\) and compute the new velocity field
\(\mathbf {v}^{n+1}\) as well as the correction pressure
\(p^{n+1}_{\text {corr}}\),
-
either by the
segregated approach: First compute the velocity predictor (
20), then solve the Poisson equation (
24),
-
or by the
coupled approach: Solve the saddle point system (
27).
In both cases, use the gradient of
\(p^{n+1}_{\text {corr}}\) to correct the velocity.
3.
Compute the dynamic pressure
\(p^{n+1}_{\text {dyn}}\) according to (
30).
4.
Update the temperature using (
32).
Now that the velocity and pressure values are known, we use the velocity field to move the point cloud, re-organize it where necessary and start the next time step. Note that we do not need to solve a non-linear equation in the whole solution process, the non-linearity is absorbed in the splitting of the pressure (the right hand side of (
30) depends non-linearly on the velocity). Instead, we need to solve three (segregated) or two (coupled) scalar Poisson-like equations as well as a three-dimensional elliptic system (segregated) or a four-dimensional saddle point system (coupled). In practice, the temperature equation as well as the vectorial velocity equation in the segregated approach can be solved easily using an one-level method like BiCGStab(2) [
15]. In the next section, we hence focus on the solution of the Poisson-like pressure equations and the saddle point systems using AMG.
2.5 Matrix properties
The matrices constructed by the finite pointset method differ in several aspects from more common finite difference, finite volume, or finite element discretization. First, as already pointed out in [
14], this discretization leads to non-symmetric matrices even for symmetric operators like the Laplacian as the point neighborhood relation is not symmetric, see Sect.
2.3. In addition, FPM employs a row-wise scaling of the matrix such that the diagonals are normalized to one.
Furthermore, the least-squares approach generally does not guarantee that all off-diagonal matrix entries are non-positive. Suchde [
17, section 2.5.5] describes a method to improve the diagonal dominance of the matrix, which in turn makes positive off-diagonal coefficients less likely, but still it is not guaranteed that no positive off-diagonal coefficients occur. This means that not only will the matrix be non-symmetric, but it also will not have the M-matrix property. Both symmetry and the M-matrix property are building blocks of most AMG convergence theories, although there has also been work on convergence theories for non-symmetric M-matrices, e.g. [
10,
11].
To the best of the authors’ knowledge, there is no method to overcome the non-symmetry of the matrix. The M-matrix property on the other hand can be ensured by using the method described in [
14], which uses a linear minimization approach instead of the least-squares approach presented in Sect.
2.3. This method ensures the M-matrix property, and, in addition it yields
minimal stencils, i.e. stencils that have a minimal number of entries among all consistent stencils. The numerical results in [
14] show that the improvements in performance of the considered AMG algorithm mostly are a consequence of the increased sparsity of the matrix, rather than a consequence of the M-matrix property. Since the linear minimization approach needs additional work in the point cloud organization and is not as general applicable as the least-squares approach in terms of boundary conditions and conditions on the point cloud, we based this work on the least-squares approach.
The boundary conditions of the partial differential equations are not eliminated from the system. For each boundary point
\(\mathbf {x}_i\) and its associated degrees of freedom, the matrix row represents the respective boundary condition discretized using the techniques described in Sect.
2.3.